Minimum insertions to form a palindrome

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

Before we go further, let us understand with few examples:

• ab: Number of insertions required is 1 i.e. bab

• aa: Number of insertions required is 0 i.e. aa

• abcd: Number of insertions required is 3 i.e. dcbabcd

• abcda: Number of insertions required is 2 i.e. adcbcda which is same as number of insertions in the substring bcd(Why?).

• abcde: Number of insertions required is 4 i.e. edcbabcde

class Solution {
    public int minInsertions(String s) {
        int n = s.length();
        int dp[][] = new int[n][n];
        // Base case when i=j
        // then number of insertions = 0
        for (int i = n - 1; i >= 0; i--) {
            for (int j = i + 1; j < n; j++) {
                dp[i][j] = 1 + Math.min(dp[i + 1][j], dp[i][j - 1]);
                if (s.charAt(i) == s.charAt(j))
                    dp[i][j] = Math.min(dp[i][j], dp[i + 1][j - 1]);
            }
        }
        return dp[0][n - 1];
    }
}