class Solution { public int minCut(String s) { /* dp playlist video 28 , 2nd approach O(n^2) */ //make boolean 2d array int n = s.length(); boolean[][] arr = new boolean[n][n]; //traversing diagonally up for(int gap = 0 ; gap < n ; gap++){ for(int i = 0 , j = gap ; j < n ; i++ , j++){ if(gap == 0) arr[i][j] = true; else if(gap == 1){ if(s.charAt(i) == s.charAt(j)) arr[i][j] = true; } else{ if(s.charAt(i) == s.charAt(j) && arr[i+1][j-1]==true) arr[i][j] = true; } } } //making 1d dp array int dp[] = new int [n]; dp[0] = 0; //0 letters need no cuts //now checking every suffix from for(int i = 1 ; i < n ; i++){ int min = Integer.MAX_VALUE; //making suffix and checking from boolean table for(int j = i ; j >= 0 ;j-- ){ //if suffix is already a pallindrome if(j==0 && arr[j][i]) min = 0; else if(arr[j][i]) min = Math.min(min , dp[j-1] + 1); } dp[i] = min; } return dp[n-1]; } }