# 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:

```python
s = "aab"
```

We can partition it as:

```python
["aa", "b"]
```

Both `"aa"` and `"b"` are palindromes.

Only one cut is needed:

```text
aa | b
```

Output:

```python
1
```

Example 2:

```python
s = "a"
```

A single character is already a palindrome.

No cut is needed.

Output:

```python
0
```

Example 3:

```python
s = "ab"
```

The whole string `"ab"` is not a palindrome.

We need to cut it into:

```python
["a", "b"]
```

Output:

```python
1
```

## Input and Output

| Item | Meaning |
|---|---|
| Input | `s: str` |
| Output | Minimum number of cuts |
| Rule | Every final substring must be a palindrome |
| Constraint | `1 <= len(s) <= 2000` |

Function shape:

```python
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:

```python
s = "aab"
```

All palindrome partitions are:

```python
["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:

```text
k - 1
```

So:

| Partition | Substrings | Cuts |
|---|---:|---:|
| `["a", "a", "b"]` | `3` | `2` |
| `["aa", "b"]` | `2` | `1` |

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:

```python
dp[i]
```

mean:

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

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

For example, if:

```python
s = "aab"
```

then:

| `i` | Prefix | `dp[i]` |
|---:|---|---:|
| `0` | `"a"` | `0` |
| `1` | `"aa"` | `0` |
| `2` | `"aab"` | `1` |

The answer is:

```python
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:

```python
is_pal[start][end]
```

meaning:

```text
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:

```python
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:

```text
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:

```python
dp[end] = 0
```

Otherwise, we cut before `start`.

The left part is:

```text
s[0:start]
```

Its minimum cuts are:

```python
dp[start - 1]
```

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

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

## Algorithm

Let `n = len(s)`.

First, build the palindrome table.

Then initialize:

```python
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:

```python
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:

```text
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:

```python
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)`.

| Phase | Time | Space |
|---|---:|---:|
| Palindrome table | `O(n^2)` | `O(n^2)` |
| Minimum cut DP | `O(n^2)` | `O(n)` |
| Total | `O(n^2)` | `O(n^2)` |

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

## Implementation

```python
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:

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

The table is filled from right to left by `start`:

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

This order ensures that when we need:

```python
is_pal[start + 1][end - 1]
```

that inner substring has already been computed.

The palindrome check is:

```python
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:

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

Otherwise, the worst case is cutting between every character:

```python
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:

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

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

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

Finally:

```python
return dp[n - 1]
```

returns the minimum cuts for the whole string.

## Testing

```python
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:

| Test | Why |
|---|---|
| `"aab"` | Standard example: `"aa" | "b"` |
| `"a"` | Single character needs no cut |
| `"ab"` | Two different characters need one cut |
| `"aba"` | Whole string is already a palindrome |
| `"aabb"` | Best partition is `"aa" | "bb"` |
| `"banana"` | Best partition is `"b" | "anana"` |
| `"abcde"` | Every character must stand alone |
| `"aaaaa"` | Whole string is palindrome |