Palindrome Partitioning: Minimum Cuts

Given a string, split it into pieces that are all palindromes, using as few cuts as possible. Return the minimum number of cuts.

LeetCode: 132. Palindrome Partitioning II

Example

Text

"aab"             ->  1   ("aa" | "b")
"ababbbabbababa"  ->  3   ("a" | "babbbab" | "b" | "ababa")
"racecar"         ->  0   (already a palindrome)

Brute force: try every palindromic prefix

Cut off a palindromic prefix and solve the rest. The answer is the best over all palindromic prefixes; a string that's a palindrome itself needs no cut.

minCuts(s, start) solves the suffix of s that begins at index start, so no substrings are copied.

Java

public class Main {
    // is s[lo..hi] (inclusive) a palindrome?
    static boolean isPalindrome(String s, int lo, int hi) {
        while (lo < hi) {
            if (s.charAt(lo++) != s.charAt(hi--)) return false;
        }
        return true;
    }

    static int minCuts(String s, int start) {
        int n = s.length();
        if (isPalindrome(s, start, n - 1)) return 0;
        int best = Integer.MAX_VALUE;
        for (int end = start; end < n - 1; end++) {      // the prefix is s[start..end]
            if (isPalindrome(s, start, end)) {
                best = Math.min(best, 1 + minCuts(s, end + 1));
            }
        }
        return best;
    }

    public static void main(String[] args) {
        System.out.println(minCuts("aab", 0) + " " + minCuts("ababbbabbababa", 0) + " " + minCuts("racecar", 0));
    }
}

Output

1 3 0

Time: exponential: every suffix is solved again for each way of reaching it, and each palindrome check costs O(n). Space: O(n) for the recursion.

The loop always finds a palindromic prefix, so best is never left at Integer.MAX_VALUE: a single character is always a palindrome, so the prefix s[start..start] always qualifies. The empty string is handled by the first check, because a range with lo >= hi is a palindrome.

Optimal: DP with a palindrome table

Two tables remove all repeated work:

pal[i][j]: is s[i..j] (inclusive) a palindrome? It is when s[i] == s[j] and the inside s[i+1..j-1] is a palindrome (or has fewer than two characters). Filling it for i from right to left makes pal[i + 1][j - 1] available when needed.
cuts[j]: the fewest cuts for the prefix s[0..j] (inclusive). If the whole prefix is a palindrome, it's 0. Otherwise, try every last piece s[i..j] that is a palindrome: cuts[j] = min(cuts[i - 1] + 1).

Java

public class Main {
    static int minCuts(String s) {
        int n = s.length();
        if (n == 0) return 0;
        boolean[][] pal = new boolean[n][n];
        for (int i = n - 1; i >= 0; i--) {
            for (int j = i; j < n; j++) {
                pal[i][j] = s.charAt(i) == s.charAt(j) && (j - i < 2 || pal[i + 1][j - 1]);
            }
        }
        int[] cuts = new int[n];
        for (int j = 0; j < n; j++) {
            if (pal[0][j]) {
                cuts[j] = 0;
            } else {
                int best = Integer.MAX_VALUE;
                for (int i = 1; i <= j; i++) {
                    if (pal[i][j]) best = Math.min(best, cuts[i - 1] + 1);
                }
                cuts[j] = best;
            }
        }
        return cuts[n - 1];
    }

    public static void main(String[] args) {
        System.out.println(minCuts("aab") + " " + minCuts("ababbbabbababa") + " " + minCuts("racecar"));
        System.out.println(minCuts("ab") + " " + minCuts(""));
    }
}

Output

1 3 0
1 0

Time: O(n²). Space: O(n²) for the palindrome table.

Edge cases

Empty string or single character: 0 cuts.
All characters different: n - 1 cuts.
Listing every partition (LeetCode 131): that's a backtracking problem. Cut off each palindromic prefix, recurse on the rest, and record the pieces when the string is used up; the pal table makes each check O(1).