minOperations_palindromic.java

public class minOperations_palindromic {

    // length of lps is inversely proportional to no of deletions / insertions

        public int minInsertions(String s) {

            return s.length() - longestPalindromeSubseq(s );
        }

        public int longestPalindromeSubseq(String s) {
            // this is basically lcs between the string and the reverse of the string.
            String reverse = new StringBuilder(s).reverse().toString();

            int m = s.length();
            int[][] dp = new int[m + 1][m + 1];

            for(int i = 1; i <= m; i++){
                for(int j = 1; j <= m; j++){
                    if(s.charAt(i - 1) == reverse.charAt(j - 1)){
                        dp[i][j] = 1 + dp[i - 1][j - 1];
                    } else {
                        dp[i][j] = Math.max(dp[i - 1][j], dp[i][j - 1]);
                    }
                }
            }

            return dp[m][m];
        }
}