Cacher is the code snippet organizer for pro developers

public int minCut(String s) {
    char[] c = s.toCharArray();
    int n = c.length;
    int[] cut = new int[n];
    boolean[][] pal = new boolean[n][n];
    
    for(int i = 0; i < n; i++) {
        int min = i;
        for(int j = 0; j <= i; j++) {
            if(c[j] == c[i] && (j + 1 > i - 1 || pal[j + 1][i - 1])) {
                pal[j][i] = true;  
                min = j == 0 ? 0 : Math.min(min, cut[j - 1] + 1);
            }
        }
        cut[i] = min;
    }
    return cut[n - 1];
}

public class Solution {
      public int minCut(String s) {
        if(s==null || s.length()==0) return 0;
        int n = s.length();
        int[] dp = new int[n];
        for(int i=0;i<n;i++) dp[i] = i;
        for(int i=0;i<n;i++) {
            extend(s, i, i, dp);
            extend(s, i, i+1, dp);
        }
        return dp[n-1];
    }
    private void extend(String s, int i, int j, int[] dp) {
        while(i >=0 && j < s.length() && s.charAt(i) == s.charAt(j)) {
            if(i==0) dp[j] = 0;
            else dp[j] = Math.min(dp[j], dp[i-1]+1);
            i--;
            j++;
        }
    }
}

public class Solution {
    public int minCut(String s) {
        if(s == null || s.length() < 2) return 0;
        char[] str = s.toCharArray();
        int len = str.length;
        int[] dp = new int[len];
        boolean[][] pal = new boolean[len][len];
        
        for (int i = len - 1; i >= 0; i--) {
            dp[i] = len - i - 1;
            for (int j = i; j  < len; j++) {
                if (str[i] == str[j] && ((j - i < 2) || pal[i + 1][j - 1])) {
                    pal[i][j] = true;
                    dp[i] = j == len - 1 ? 0 : Math.min(dp[i], dp[j + 1] + 1);
                    
                }
            }
        }
        return dp[0];
    }
}

public class Solution {
    private boolean isPalindrome(StringBuilder sb) {
        if (sb.length() < 2) return true;
        int i = 0;
        int j = sb.length() - 1;
        while (i < j) {
            if (sb.charAt(i) != sb.charAt(j)) return false;
            i++;
            j--;
        }
        return true;
    }
    private void backtracking(char[] str, int idx, int[] cnt) {
        if (idx == str.length) {
            cnt[1] = Math.min(cnt[1], cnt[0]);
        }
        
        StringBuilder sb = new StringBuilder();
        for (int i = idx; i < str.length; i++) {
            sb.append(str[i]);
            if (isPalindrome(sb)) {
                cnt[0]++;
                backtracking(str, i + 1, cnt);
                cnt[0]--;
            }
        }
    }
    public int minCut(String s) {
        int[] cnt = new int[2];
        cnt[1] = Integer.MAX_VALUE;
        backtracking(s.toCharArray(), 0, cnt);
        return cnt[1] - 1;
    }
}

/*"ababababababababababababcbabababababababababababa"*/