Palindrome Partitioning Problem

Problem Statement

Given a string s, find the minimum number of cuts needed to partition the string such that every substring in the partition is a palindrome.

Example:

• Input: s = "aab"

• Output: 1

• Explanation: One cut: "aa" | "b". Both "aa" and "b" are palindromes.

• Input: s = "abcba"

• Output: 0

• Explanation: The entire string is already a palindrome, so no cuts needed.

Noob-Friendly Explanation

Imagine you have a ribbon with letters written on it. You need to cut the ribbon into pieces such that each piece reads the same forwards and backwards (palindrome). What's the minimum number of cuts you need?

For "aab": if you cut between the second a and b, you get "aa" (palindrome!) and "b" (palindrome!). That's just 1 cut. You can't do it with 0 cuts because "aab" isn't a palindrome.

Approach 1: Brute Force (Recursion)

Intuition

Try every possible position for the first cut. For each cut, if the left part is a palindrome, recursively find the minimum cuts for the right part.

Algorithm

1. If the entire string is a palindrome, return 0.
2. Try every cut position i. If s[0..i] is a palindrome, recursively solve for s[i+1..n-1] and add 1 cut.
3. Return the minimum cuts found.

class Solution {
    public int minCuts(String s) {
        return solve(s, 0, s.length() - 1);
    }

    private int solve(String s, int i, int j) {
        if (i >= j || isPalindrome(s, i, j)) return 0;

        int minCuts = Integer.MAX_VALUE;

        for (int k = i; k < j; k++) {
            if (isPalindrome(s, i, k)) {
                int cuts = 1 + solve(s, k + 1, j);
                minCuts = Math.min(minCuts, cuts);
            }
        }

        return minCuts;
    }

    private boolean isPalindrome(String s, int left, int right) {
        while (left < right) {
            if (s.charAt(left) != s.charAt(right)) return false;
            left++;
            right--;
        }
        return true;
    }
}

Complexity Analysis

• Time Complexity: O(2^n) - In the worst case, we try all possible partitions.
• Space Complexity: O(n) - Recursion stack depth.

Approach 2: Optimal (Dynamic Programming)

Intuition

We use two DP tables: one to precompute which substrings are palindromes, and another to find the minimum cuts. cuts[i] = minimum cuts for substring s[0..i].

Algorithm

1. Precompute isPalin[i][j] = true if s[i..j] is a palindrome (using DP).
2. Create cuts[i] = minimum cuts for s[0..i].
3. If s[0..i] is a palindrome, cuts[i] = 0.
4. Otherwise, try every j from 0 to i-1: if s[j+1..i] is a palindrome, cuts[i] = min(cuts[i], cuts[j] + 1).

class Solution {
    public int minCuts(String s) {
        int n = s.length();

        // Step 1: Precompute palindrome table
        boolean[][] isPalin = new boolean[n][n];
        for (int i = n - 1; i >= 0; i--) {
            for (int j = i; j < n; j++) {
                if (s.charAt(i) == s.charAt(j)) {
                    if (j - i <= 2) {
                        isPalin[i][j] = true;
                    } else {
                        isPalin[i][j] = isPalin[i + 1][j - 1];
                    }
                }
            }
        }

        // Step 2: Find minimum cuts
        int[] cuts = new int[n];
        for (int i = 0; i < n; i++) {
            if (isPalin[0][i]) {
                cuts[i] = 0; // Whole substring is palindrome
            } else {
                cuts[i] = Integer.MAX_VALUE;
                for (int j = 0; j < i; j++) {
                    if (isPalin[j + 1][i]) {
                        cuts[i] = Math.min(cuts[i], cuts[j] + 1);
                    }
                }
            }
        }

        return cuts[n - 1];
    }
}

Complexity Analysis

• Time Complexity: O(n^2) - Precomputing palindromes takes O(n^2) and finding cuts takes O(n^2).
• Space Complexity: O(n^2) - For the palindrome table.