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];
    }

    //Memoized -> n^3
    //https://leetcode.com/problems/palindrome-partitioning-ii/solutions/1267844/java-recursion-memoization-optimized-matrix-chain-multiplication-approach-with-code-mcm/
    
    /* front partioning-> we save the left call by only calling when left part is a pallindrome , as that will only
    give us the min cuts , we call right when left is a pallin , saving us a full left recursion call
    */
    public int solve(String str , int i , int j , Integer[][] dp){
        if(i >=j)
        return 0;

        if(dp[i][j] != null)
        return dp[i][j];

        if(pallin(str,i,j))
        return dp[i][j] = 0;
    
        else{
            int min = (int)1e9;

            for(int k = i ; k < j ;k++){
                //checking if left part is a pallindrome
                if(pallin(str,i,k)){
                    int right = 1 + solve(str ,k+1 , j , dp);
                    min = Math.min(min , right);
                }
            }
            return dp[i][j] = min;
        }
    }
    public boolean pallin(String str , int i , int j){
        while(i <= j){
            char ch1 = str.charAt(i) , ch2 = str.charAt(j);

            if(ch1 != ch2)
            return false;
            
            i++;
            j--;
        }
        return true;
    }
}