class Solution { public int minInsertions(String s) { /* Q60 of dp playlist , find longest pallindromic subsequnce then minimum insertion to make strings pallindromic becomes str.length() - LPS; */ //code of LPS int n = s.length(); int[][] dp = new int[n][n]; for(int gap = 0 ; gap < n ; gap++){ for(int i = 0 , j = gap ; j < n ; j++,i++){ if(gap == 0) dp[i][j] = 1; else if(gap == 1) dp[i][j] = s.charAt(i)==s.charAt(j) ? 2 :1; else{ char ch1 = s.charAt(i) , ch2 = s.charAt(j); if(ch1 == ch2) dp[i][j] = dp[i+1][j-1] + 2; else dp[i][j] = Math.max(dp[i][j-1] , dp[i+1][j]); } } } //minimum insertions becomes return s.length() - dp[0][n-1]; } }