Palindrome Partitioning II

Palindrome Partitioning II asks for the minimum number of cuts to break a string into palindromic pieces. It is a clean two-layer dynamic-programming problem: a table that answers "is this slice a palindrome?" feeding a one-dimensional DP that answers "how few cuts for this prefix?"

The slow way first

The brute force tries every possible way to slice the string and checks each piece. The number of partitions is exponential, so this blows up fast. Even just re-checking "is this slice a palindrome?" over and over wastes work.

The question to ask: can I reuse answers for shorter prefixes? The minimum cuts for "aab" clearly depends on the minimum cuts for "aa" and "a". That overlap is the signal to use DP.

The idea: a palindrome table feeding a cuts array

Two pieces.

First, precompute isPal[i][j] — true if s[i..j] is a palindrome. This is itself a small DP: a slice is a palindrome when its ends match and the inside is already a palindrome.

Second, fill dp[i] = minimum cuts for the first i characters. Start with dp[0] = 0. For each prefix length i, try every cut point j: if the right piece s[j..i-1] is a palindrome, the cost is dp[j] + 1 (one cut before it), or 0 if the whole prefix is itself a palindrome. Take the smallest.

The answer is dp[n], the minimum cuts for the entire string.

Walk through it

Step through the animation on s = "aab". The i pointer marks the prefix end, and j slides to each cut point. For prefixes "a" and "aa" the whole thing is a palindrome, so dp = 0. For "aab", the split "aa" | "b" works with one cut, giving dp[3] = 1.

Pseudocode

n = length of s
isPal[i][j] = true when s[i..j] is a palindrome   # precomputed table
dp[0] = 0; dp[1..n] = infinity                    # min cuts per prefix
for i from 1 to n:                                # prefix of length i
    for j from 0 to i - 1:                        # try every cut point
        if isPal[j][i - 1]:                       # right piece is a palindrome
            cost = 0 if j == 0 else dp[j] + 1     # whole prefix, or one cut
            dp[i] = min(dp[i], cost)
return dp[n]

The Python solution

def min_cut(s):
    n = len(s)
    is_pal = build_palindrome_table(s)
    dp = [0] + [float("inf")] * n
    for i in range(1, n + 1):
        for j in range(i):
            if is_pal[j][i - 1]:
                cost = 0 if j == 0 else dp[j] + 1
                dp[i] = min(dp[i], cost)
    return dp[n]

• is_pal[j][i - 1] is the precomputed table: true when the slice s[j..i-1] is a palindrome.
• dp has n + 1 slots; dp[0] = 0 is the empty prefix and the rest start at infinity.
• The outer loop fixes the prefix length i; the inner loop tries every cut point j.
• Line 8 is the heart: if j == 0 the whole prefix is one palindrome (no cut), otherwise it costs dp[j] + 1.
• We keep the smallest cost over all valid j, and dp[n] is the answer.

Complexity

Both the palindrome table and the cuts loop are O(n^2). The table costs O(n^2) space; the dp array adds only O(n).

When this pattern shows up

Practice