LeetCode 132: Palindrome Partitioning II

Problem Restatement

We are given a string s.

We need to cut the string into substrings so that every substring is a palindrome.

Return the minimum number of cuts needed.

LeetCode states the problem as partitioning s so every substring is a palindrome, then returning the minimum cuts needed for such a palindrome partitioning. The constraints are 1 <= s.length <= 2000, and s contains lowercase English letters only.

Examples

Example 1:

s = "aab"

We can partition it as:

["aa", "b"]

Both "aa" and "b" are palindromes.

Only one cut is needed:

aa | b

Output:

1

Example 2:

s = "a"

A single character is already a palindrome.

No cut is needed.

Output:

0

Example 3:

s = "ab"

The whole string "ab" is not a palindrome.

We need to cut it into:

["a", "b"]

Output:

1

Input and Output

Function shape:

class Solution:
    def minCut(self, s: str) -> int:
        ...

First Thought: Generate All Partitions

From LeetCode 131, we know how to generate all palindrome partitions.

For example:

s = "aab"

All palindrome partitions are:

["a", "a", "b"]
["aa", "b"]

Then we could count cuts in each partition and take the minimum.

For a partition with k substrings, the number of cuts is:

k - 1

So:

This works for small strings, but it is too slow because the number of partitions can be exponential.

We need dynamic programming.

Key Insight

The problem asks for the minimum number of cuts, not the actual partitions.

So we only need the best answer for each prefix.

Let:

dp[i]

mean:

minimum cuts needed for s[0:i+1]

That is, dp[i] solves the prefix ending at index i.

For example, if:

s = "aab"

then:

The answer is:

dp[n - 1]

Palindrome Precomputation

To compute dp, we need to quickly know whether any substring s[start:end+1] is a palindrome.

We precompute a table:

is_pal[start][end]

meaning:

s[start:end+1] is a palindrome

A substring is a palindrome if:

1. Its first and last characters are equal.
2. Its inside substring is also a palindrome.

So the recurrence is:

is_pal[start][end] = (
    s[start] == s[end]
    and (end - start <= 2 or is_pal[start + 1][end - 1])
)

The condition end - start <= 2 handles substrings of length 1, 2, and 3.

DP Transition

Suppose we want to compute dp[end].

We try every possible start index start for the last palindrome block:

s[start:end+1]

If s[start:end+1] is a palindrome, then the last block can be this substring.

There are two cases.

If start == 0, the whole prefix s[0:end+1] is a palindrome.

So no cut is needed:

dp[end] = 0

Otherwise, we cut before start.

The left part is:

s[0:start]

Its minimum cuts are:

dp[start - 1]

Then we add one cut between the left part and the last palindrome block:

dp[end] = min(dp[end], dp[start - 1] + 1)

Algorithm

Let n = len(s).

First, build the palindrome table.

Then initialize:

dp = [0] * n

For each end from 0 to n - 1:

1. If s[0:end+1] is a palindrome, set dp[end] = 0.
2. Otherwise, try every start from 1 to end.
3. If s[start:end+1] is a palindrome, update:

dp[end] = min(dp[end], dp[start - 1] + 1)

Return dp[n - 1].

Correctness

The palindrome table is correct because it follows the definition of a palindrome. A substring with matching ends is a palindrome exactly when its inner substring is a palindrome, with length 1, 2, and 3 handled directly.

For the dynamic programming part, consider an optimal palindrome partition of the prefix s[0:end+1].

Its last block must be some palindrome substring:

s[start:end+1]

If start == 0, then the whole prefix is one palindrome and the answer is 0.

If start > 0, then there must be one cut before start. The part before that cut is s[0:start], whose optimal value is dp[start - 1]. Therefore, this partition uses:

dp[start - 1] + 1

cuts.

The algorithm tries every possible start whose last block is a palindrome, so it considers the last block of the optimal solution. It takes the minimum over all such choices, so dp[end] equals the minimum cuts needed for s[0:end+1].

Thus, dp[n - 1] is the minimum number of cuts for the whole string.

Complexity

Let n = len(s).

With n <= 2000, this fits the intended dynamic programming approach.

Implementation

class Solution:
    def minCut(self, s: str) -> int:
        n = len(s)

        is_pal = [[False] * n for _ in range(n)]

        for start in range(n - 1, -1, -1):
            for end in range(start, n):
                if s[start] == s[end] and (
                    end - start <= 2 or is_pal[start + 1][end - 1]
                ):
                    is_pal[start][end] = True

        dp = [0] * n

        for end in range(n):
            if is_pal[0][end]:
                dp[end] = 0
                continue

            best = end

            for start in range(1, end + 1):
                if is_pal[start][end]:
                    best = min(best, dp[start - 1] + 1)

            dp[end] = best

        return dp[n - 1]

Code Explanation

We first build a table for palindrome checks:

is_pal = [[False] * n for _ in range(n)]

The table is filled from right to left by start:

for start in range(n - 1, -1, -1):

This order ensures that when we need:

is_pal[start + 1][end - 1]

that inner substring has already been computed.

The palindrome check is:

if s[start] == s[end] and (
    end - start <= 2 or is_pal[start + 1][end - 1]
):
    is_pal[start][end] = True

Then dp[end] stores the minimum cuts for the prefix ending at end.

If the whole prefix is already a palindrome:

if is_pal[0][end]:
    dp[end] = 0
    continue

Otherwise, the worst case is cutting between every character:

best = end

For a prefix of length end + 1, the maximum needed cuts is end.

Then we try each possible starting index of the last palindrome block:

for start in range(1, end + 1):

If that last block is a palindrome, we update the answer:

best = min(best, dp[start - 1] + 1)

Finally:

return dp[n - 1]

returns the minimum cuts for the whole string.

Testing

def run_tests():
    s = Solution()

    assert s.minCut("aab") == 1
    assert s.minCut("a") == 0
    assert s.minCut("ab") == 1
    assert s.minCut("aba") == 0
    assert s.minCut("aabb") == 1
    assert s.minCut("banana") == 1
    assert s.minCut("abcde") == 4
    assert s.minCut("aaaaa") == 0

    print("all tests passed")

run_tests()

Test meaning: