Given a string s, partition s such that every substring of the partition is a palindrome.

Return the minimum cuts needed for a palindrome partitioning of s.

&nbsp;
Example 1:

Input: s = "aab"
Output: 1
Explanation: The palindrome partitioning ["aa","b"] could be produced using 1 cut.


Example 2:

Input: s = "a"
Output: 0


Example 3:

Input: s = "ab"
Output: 1


&nbsp;
Constraints:


	1 &lt;= s.length &lt;= 2000
	s consists of lowercase English letters only.


class Solution:
    def isPallindrom(self, s: str, l, r) -> bool:
        st = s[l: r+1]
        rev = st[::-1]
        return st == rev
    
    def minCut(self, s: str) -> int:
        N = len(s)
        if not s: return 0
        if self.isPallindrom(s, 0, N-1): return 0
        dp = [sys.maxsize] * (N+1)
        dp[-1] = 0
        
        for i in range(N-1, -1, -1):
            for j in range(i, N):
                if self.isPallindrom(s, i, j):
                    dp[i] = min(dp[i], 1 + dp[j+1])
                    
        return dp[0]-1
class Solution {
int dp[];

 public boolean pali(int i,int j,String s){
    
   // int j=s.length()-1,i=0;
    
    while(i<=j){
        
        if(s.charAt(i)!=s.charAt(j))return false;
            
            i++;j--;
        
    }
    
    return true;
    
}
public int cut(String s,int i,int n,int dp[]){
    
    if(i==n)return 0;
    if(dp[i]!=-1)return dp[i];
    
    int min=Integer.MAX_VALUE;
    
    for(int j=i;j<n;j++){
        
        if(pali(i,j,s)){
            
            int cost=1+cut(s,j+1,n,dp);
            min=Math.min(min,cost);
            
      } 
    }
   return  dp[i]=min;
       
public int minCut(String s) {
    int n=s.length();
    dp=new int[n];
    Arrays.fill(dp,-1);
    return cut(s,0,n,dp)-1;       
}
class Solution {
public:
    
	// function to precompute if every substring of s is a palindrome or not
    vector<vector<bool>> isPalindrome(string& s){
        int n = s.size();
        vector<vector<bool>> dp(n, vector<bool>(n, false));
        
        for(int i=0; i<n; i++){
            dp[i][i] = true;
        }
        
        for(int i=0; i<n-1; i++){
            if(s[i] == s[i+1]){
                dp[i][i+1] = true;
            }
        }
        
        int k = 2;
        
        while(k < n){
            int i=0;
            int j=k;
            
            while(j<n){
                if(s[i] == s[j] and dp[i+1][j-1]){
                    dp[i][j] = true;
                }
                
                i++;
                j++;
            }
            
            k++;
        }
        
        return dp;
    }
    
	// function to find the minimum palindromic substrings in s
    int solve(string& s, int n, int i, vector<vector<bool>>& palin, vector<int>& memo){
        if(i==n){
            return 0;
        }
        if(memo[i] != -1){
            return memo[i];
        }
        
        int result = INT_MAX;
        
        for(int j=i+1; j<=n; j++){
            if(palin[i][j-1]){
                result = min(result, 1+solve(s, n, j, palin, memo));
            }
        }
        
        return memo[i] = result;
    }
    
    int minCut(string s) {
        int n = s.size();
        vector<int> memo(n, -1);
        vector<vector<bool>> palin = isPalindrome(s);
        return solve(s, n, 0, palin, memo)-1;
    }
};
var minCut = function(s) {
    function isPal(l, r) {
        while (l < r) {
            if (s[l] === s[r]) l++, r--;
            else return false;
        } return true;
    }

    let map = new Map();
    function dfs(idx = 0) {
        if (idx === s.length) return 0;
        if (map.has(idx)) return map.get(idx);
        let min = Infinity;
        for (let i = idx; i < s.length; i++) {
            if (isPal(idx, i)) min = Math.min(min, 1 + dfs(i + 1));
        }
        map.set(idx, min);
        return min;
    }

    return dfs() - 1;
};
Palindrome Partitioning II