Problem

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.

Examples

Example 1:

Input:
s = "zzazz"
Output:
 0
Explanation: The string "zzazz" is already palindrome we don't 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".

Solution

Method 1 - Recursion

The minimum number of insertions in the string str[i...j] can be given as:

  • minInsertions(str[i + 1...j - 1]) if str[i] is equal to str[j]
  • min(minInsertions(str[i...j - 1]), minInsertions(str[i + 1...j])) + 1 otherwise

Code

Java
class Solution {

	public int minInsertions(String s) {
		return helper(s, 0, s.length() - 1, memo);
	}

	private int helper(String s, int i, int j) {
		if (i >= j) {
			return 0;
		}

		return s.charAt(i) == s.charAt(j) ? helper(s, i + 1, j - 1) : 1 + Math.min(helper(s, i + 1, j), helper(s, i, j - 1));
	}
}

Method 2 - Top Down DP

If we observe the above approach carefully, we can find that it exhibits overlapping subproblems. Suppose we want to find the minimum number of insertions in string “abcde”:

graph TD;

T(fabcdef) --- A(abcde)
A --- B(bcde) & C(abcd)
B --- D(cde) & E(bcd)
C --- F(bcd) & G(abc)
D --- H(de) & I(cd)
E --- J(cd) & K(bc)
F --- L(...)
G --- M(...)
H --- N(...)
I --- O(...)
J --- P(...)
K --- Q(...)

style E fill:#00758f
style F fill:#00758f
style I fill:#010aaa
style J fill:#010aaa

Code

C++
class Solution {
public:
    vector<vector<int>> memo;
    int dp(string &s,int i,int j)
    {
        if(i>=j)							//Base case.
            return 0;
        if(memo[i][j]!=-1)					//Check if we have already calculated the value for the pair `i` and `j`.
            return memo[i][j];
        return memo[i][j]=s[i]==s[j]?dp(s,i+1,j-1):1+min(dp(s,i+1,j),dp(s,i,j-1));		//Recursion as mentioned above.
    }
    int minInsertions(string s) 
    {
        memo.resize(s.length(),vector<int>(s.length(),-1));
        return dp(s,0,s.length()-1);
    }
};
Java
class Solution {

	public int minInsertions(String s) {
		int n = s.length();
		Integer[][] memo = new Integer[n][n];
		return helper(s, 0, n - 1, memo);
	}

	private int helper(String s, int i, int j, Integer[][] memo) {
		if (i >= j) { //Base case.
			return 0;
		}

		if (memo[i][j] != null) {
			return memo[i][j];
		}

		return memo[i][j] = s.charAt(i) == s.charAt(j) ? helper(s, i + 1, j - 1, memo) : 1 + Math.min(helper(s, i + 1, j, memo), helper(s, i, j - 1, memo));
	}
}

Method 3 - Bottom-up DP

Code

Java
class Solution {

	public int minInsertions(String s) {
		int n = s.length();
		int[][] dp = new int[n][n];
		// Length of substring (2 to n)
		for (int len = 2; len <= n; len++) {
			// i = Starting index of substring
			for (int i = 0; i + len - 1 < n; i++) {
			    // j - Ending index of substring
				int j = i + len - 1;
				// If characters match, use previous result
				if (s.charAt(i) == s.charAt(j)) {
					dp[i][j] = dp[i + 1][j - 1];
				} else {
					// Minimum insertions from either side
					dp[i][j] = 1 + Math.min(dp[i + 1][j], dp[i][j - 1]);
				}
			}
		}

		return dp[0][n - 1];
	}

}