Minimum Insertion Steps to Make a String Palindrome

Given a string s. In one step you can insert any character at any index of the string.

Return the minimum number of steps to make s palindrome.

A Palindrome String is one that reads the same backward as well as forward.

Example 1:

Input: s = “zzazz”
Output: 0
Explanation: The string “zzazz” is already palindrome we do not need any insertions.

Example 2:

Input: s = “mbadm”
Output: 2
Explanation: String can be “mbdadbm” or “mdbabdm”.

Example 3:

Input: s = “leetcode”
Output: 5
Explanation: Inserting 5 characters the string becomes “leetcodocteel”.

Constraints:

• 1 <= s.length <= 500
• s consists of lowercase English letters.

Approach - Tabulation 1D

• We convert the 2D to 1D
  • dp[j] (before overwrite) = dp[i+1][j]
  • dp[j-1] (just overwritten) = dp[i][j-1]
  • prev = dp[i+1][j-1]
• Think of this way when we do this 2D to 1D it is like we go through the same row again and again now if we want what was there on the same column in the last row then it is like asking what is the last value in current index as we only have one row
• If we ask what is the value one column back then it is just last index since we have one row but column are same as before
• O(n^2), O(n)

class Solution {
    public int minInsertions(String s) {
        int n = s.length();
        int[] dp = new int[n];
 
        for (int i = n - 2; i >= 0; i--) {
            int prev = 0;
            for (int j = i + 1; j < n; j++) {
                int tmp = dp[j];
                if (s.charAt(i) == s.charAt(j))
                    dp[j] = prev;
                else
                    dp[j] = 1 + Math.min(dp[j], dp[j-1]);
                prev = tmp;
            }
        }
        return dp[n - 1];
    }
}

Approach - Tabulation 2D

• Similar approach everywhere just remember i-1 and j+1 because first loop backwards and second forward
• O(n^2), O(n^2)

class Solution {
    public int minInsertions(String s) {
        int n = s.length();
        int[][] dp = new int[n][n];
 
        for (int i = n - 1; i >= 0; i--) {
            for (int j = i + 1; j < n; j++) {
                if (s.charAt(i) == s.charAt(j))
                    dp[i][j] = dp[i+1][j-1];
                else
                    dp[i][j] = 1 + Math.min(dp[i+1][j], dp[i][j-1]);
            }
        }
 
        return dp[0][n-1];
    }
}

Approach - Memoization 2D

• We just memoize the below solution using 2D DP
• O(n^2), O(n^2)

class Solution {
    int[][] dp;
    public int minInsertions(String s) {
        dp = new int[s.length() +1][s.length() + 1];
        for (int[] a: dp)
            Arrays.fill(a, -1);
 
        return solve(s, 0, s.length() - 1);
    }
 
    public int solve(String s, int i, int j) {
        if (i >= j)
            return 0;
        
        if (dp[i][j] != -1)
            return dp[i][j];
 
        if (s.charAt(i) == s.charAt(j))
            return dp[i][j] = solve(s, i+1, j-1);
        else
            return dp[i][j] = 1 + Math.min(solve(s, i+1, j), solve(s, i, j-1));
    }
}

Approach - Recursion

• We have simple tree where we take 2 pointer one from start and other from the end now what we do is if characters match at both index then we solve for i+1 and j-1
• If they are not equal then we have to do insertion and move to the next so we find minimum between i+1 and j-1 and add 1 for insertion
• O(2^n), O(1)

class Solution {
    public int minInsertions(String s) {
        return solve(s, 0, s.length() - 1);
    }
 
    public int solve(String s, int i, int j) {
        if (i >= j)
            return 0;
 
        if (s.charAt(i) == s.charAt(j))
            return solve(s, i+1, j-1);
        else
            return 1 + Math.min(solve(s, i+1, j), solve(s, i, j-1));
    }
}