1. class Solution {
  2.     /**
  3.     To make a string a palindrome with minimum insertions, 
  4.     we try to keep the largest palindromic part of the string unchanged and insert characters for the rest.
  5.     Minimum Insertions=n−LPS length
  6.     Minimum Deletion=n−LPS length
  7.     1. Reverse the string and store it in new string
  8.     2. Find Longest Common Subsequence (LCS) between s and reverse(s).
  9.     3. That LCS is the Longest Palindromic Subsequence.
  10.     */
  11.     public int minInsertions(String s) {
  12.         String s2 = new StringBuilder(s).reverse().toString();
  13.  
  14.         int n = s.length();
  15.         int m = s2.length();
  16.  
  17.         // create a matrix
  18.         int[][] t = new int[n+1][m+1];
  19.  
  20.         // initialise the matrix
  21.         for(int i=0; i<n+1; i++)
  22.         {
  23.             for(int j=0; j<m+1; j++)
  24.             {
  25.                 if(i == 0 || j == 0)
  26.                     t[i][j] = 0;
  27.             }
  28.         }
  29.  
  30.         // find LCS
  31.         for(int i=1; i<n+1; i++)
  32.         {
  33.             for(int j=1; j<m+1; j++)
  34.             {
  35.                 if(s.charAt(i-1) == s2.charAt(j-1))
  36.                 {
  37.                     t[i][j] = 1 + t[i-1][j-1];
  38.                 }
  39.                 else
  40.                     t[i][j] = Math.max(t[i-1][j], t[i][j-1]);
  41.             }
  42.         }
  43.  
  44.         int lcsLength = t[n][m];
  45.         return (n-lcsLength);
  46.     }
  47. }
  48.  
  49.  
  50. // s= zzazz
  51. // t= zzazz
  52.  
  53. // LCS: zzazz
  54.  
  55. // s= mbadm
  56. // t= mdabm
  57. // LCS: mam = 3
  58. // No of deletion = n-lcs = 5-3 = 2
  59. // no of insertion = m - lcs = 5-3 = 2