[Solved] Minimum Steps Given a string str, Your task here is to find the minimum number of characters to be inserted to convert it to palindrome

Minimum Steps: Given a string str, Your task here is to find the minimum number of characters to be inserted to convert it to palindrome.

Input Format

Single line containing a String s

Constraints

1 <= s.length <= 50

All characters of s are lower case English letters.

Output Format

The minimum number of steps to make s palindrome

Evaluation Parameters

input:

doselect

Output:

5

Solution

The idea is to use Dynamic Programming. We define the state dp[i][j] to be the minimum number of insertions to make the substring str[i..j] a palindrome. Then the state equations are:

dp[i][j] = dp[i+1][j-1], if str[i] == str[j]

dp[i][j] = min(dp[i][j-1], dp[i+1][j]) + 1, otherwise

The base cases are:

dp[i][i] = 0, for all i

dp[i][i+1] = 0, if str[i] == str[i+1]

dp[i][i+1] = 1, otherwise

The answer is dp[0][n-1].

Time Complexity: O(n^2)

public static int minInsertions(String s) {
        int n = s.length();
        int[][] dp = new int[n+1][n+1];
        for (int i = 0; i < n; ++i)
            for (int j = 0; j < n; ++j)
                dp[i + 1][j + 1] = s.charAt(i) == s.charAt(n - 1 - j) ? dp[i][j] + 1 : Math.max(dp[i][j + 1], dp[i + 1][j]);
        return n - dp[n][n];
    }

// C++
int MinimumSteps(string s){
    int dp[s.length()][s.length()];
    for(int i=0; i < s.length(); i++){
        dp[i][i] = 1;
    }
    for( int i=2;i<=s.length();i++) {
        for (int temp = 0; temp < s.length()-i+1; temp++) {
            int j=temp+i-1;
            if(s[temp]==s[j]) dp[temp][j]=dp[temp+1][j-1]+2;
            else {
                dp[temp][j]=max(dp[temp + 1][j], dp[temp][j - 1]);
            }
        }
    }
    return (s.length()-dp[0][s.length()-1]);
}

def MinimumSteps(s):
    dp = [[0 for i in range(len(s))] for j in range(len(s))]
    for i in range(len(s)):
        dp[i][i] = 1
    for i in range(2, len(s)+1):
        for j in range(len(s)-i+1):
            if s[j] == s[j+i-1]:
                dp[j][j+i-1] = dp[j+1][j+i-2] + 2
            else:
                dp[j][j+i-1] = max(dp[j+1][j+i-1], dp[j][j+i-2])
    return len(s) - dp[0][len(s)-1]

Happy Learning – If you require any further information, feel free to contact me.