Palindrome Partitioning II [Min cuts]

XXX. Palindrome Partitioning II

Dynamic Programming

Palindrome

Problem Statement:

Given a string s, partition it such that every substring of the partition is a palindrome. Return the minimum cuts needed for a palindrome partitioning of s.

Algorithm:

1. Use a 2D boolean array pal to track if a substring s[j:i] is a palindrome.
2. Maintain a 1D array cut where cut[i] stores the minimum cuts needed for a palindrome partitioning of the first i+1 characters.
3. Iterate through the string and for each character, check all possible substrings ending at the current character.
4. If a substring is a palindrome, update the cut array by checking the minimum cuts required.

Complexity:

Time Complexity: O(n²), where n is the length of the string. This accounts for the nested loops to check substrings and update the cut array.
Space Complexity: O(n²) for the pal array and O(n) for the cut array.

Java Implementation:

class Solution {
    public int minCut(String s) {
        int n = s.length();
        int[] cut = new int[n]; // Minimum cuts needed for first i+1 characters
        boolean[][] pal = new boolean[n][n]; // pal[j][i] indicates if s[j:i+1] is a palindrome

        for (int i = 0; i < n; i++) {
            int min = i; // Maximum cuts needed is i (cut every character)
            for (int j = 0; j <= i; j++) {
                if (s.charAt(j) == s.charAt(i) && (i - j <= 2 || pal[j + 1][i - 1])) {
                    pal[j][i] = true; // Substring s[j:i+1] is a palindrome
                    min = j == 0 ? 0 : Math.min(min, cut[j - 1] + 1);
                }
            }
            cut[i] = min; // Store the minimum cuts needed for s[0:i+1]
        }
        return cut[n - 1]; // Return the minimum cuts needed for the entire string
    }
}
                

Python Implementation:

def minCut(s: str) -> int:
    n = len(s)
    cut = [0] * n  # Minimum cuts needed for first i+1 characters
    pal = [[False] * n for _ in range(n)]  # pal[j][i] indicates if s[j:i+1] is a palindrome

    for i in range(n):
        min_cut = i  # Maximum cuts needed is i (cut every character)
        for j in range(i + 1):
            if s[j] == s[i] and (i - j <= 2 or pal[j + 1][i - 1]):
                pal[j][i] = True  # Substring s[j:i+1] is a palindrome
                min_cut = 0 if j == 0 else min(min_cut, cut[j - 1] + 1)
        cut[i] = min_cut  # Store the minimum cuts needed for s[0:i+1]

    return cut[-1]  # Return the minimum cuts needed for the entire string
                

C++ Implementation:

#include 
#include 
#include 
using namespace std;

class Solution {
public:
    int minCut(string s) {
        int n = s.size();
        vector cut(n, 0); // Minimum cuts needed for first i+1 characters
        vector> pal(n, vector(n, false)); // pal[j][i] indicates if s[j:i+1] is a palindrome

        for (int i = 0; i < n; i++) {
            int min_cut = i; // Maximum cuts needed is i (cut every character)
            for (int j = 0; j <= i; j++) {
                if (s[j] == s[i] && (i - j <= 2 || pal[j + 1][i - 1])) {
                    pal[j][i] = true; // Substring s[j:i+1] is a palindrome
                    min_cut = j == 0 ? 0 : min(min_cut, cut[j - 1] + 1);
                }
            }
            cut[i] = min_cut; // Store the minimum cuts needed for s[0:i+1]
        }
        return cut[n - 1]; // Return the minimum cuts needed for the entire string
    }
};