# LeetCode 131: Palindrome Partitioning

## Problem Restatement

We are given a string `s`.

We need to split it into substrings so that every substring is a palindrome.

Return all possible palindrome partitionings of `s`.

A palindrome is a string that reads the same forward and backward, such as:

```text
"a"
"aa"
"aba"
"racecar"
```

LeetCode states the task as: partition `s` so every substring of the partition is a palindrome, then return all possible palindrome partitioning of `s`.

## Examples

Example 1:

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

Possible partitions:

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

Both are valid because every substring is a palindrome.

Output:

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

Example 2:

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

The only partition is:

```python
["a"]
```

Output:

```python
[["a"]]
```

## Input and Output

| Item | Meaning |
|---|---|
| Input | `s: str` |
| Output | `list[list[str]]` |
| Rule | Every substring in each partition must be a palindrome |
| Order | Any valid order is accepted |

Function shape:

```python
class Solution:
    def partition(self, s: str) -> list[list[str]]:
        ...
```

## First Thought: Try Every Cut

A string of length `n` has `n - 1` gaps between characters.

For each gap, we can either cut or not cut.

For example:

```text
a a b
```

There are two gaps:

```text
a | a | b
a | ab
aa | b
aab
```

Then we keep only partitions where every piece is a palindrome.

This gives the right intuition, but we need a clean recursive way to generate only valid partitions.

## Key Insight

At any index `start`, choose the next substring.

For example, with:

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

At `start = 0`, possible next substrings are:

```python
"a"
"aa"
"aab"
```

Only `"a"` and `"aa"` are palindromes.

So we try:

```text
choose "a", then partition the rest: "ab"
choose "aa", then partition the rest: "b"
```

This is a backtracking problem.

We make one valid choice, recurse on the remaining suffix, then undo the choice and try another one.

## Palindrome Precomputation

If we check whether each substring is a palindrome by scanning it every time, we repeat work.

We can precompute a table:

```python
is_pal[i][j]
```

meaning:

```text
s[i:j+1] is a palindrome
```

A substring is a palindrome when:

1. Its two ends match.
2. The inside substring is also a palindrome.

So:

```python
is_pal[i][j] = s[i] == s[j] and (j - i <= 2 or is_pal[i + 1][j - 1])
```

The condition `j - i <= 2` covers lengths `1`, `2`, and `3`.

Examples:

| Substring length | Rule |
|---:|---|
| `1` | Always palindrome |
| `2` | Palindrome if both chars match |
| `3` | Palindrome if first and last chars match |
| `4+` | Ends must match and inside must be palindrome |

## Algorithm

Let `n = len(s)`.

First, build the palindrome table.

Then run DFS:

```python
dfs(start)
```

where `start` is the first index not yet partitioned.

For each `end` from `start` to `n - 1`:

1. Check if `s[start:end+1]` is a palindrome.
2. If yes, append it to the current path.
3. Recurse from `end + 1`.
4. Pop it from the path.

When `start == n`, the whole string has been partitioned. Add a copy of the current path to the answer.

## Correctness

The DFS considers every possible next substring starting at the current index.

It only chooses a substring when `is_pal[start][end]` is true, so every substring added to the path is a palindrome.

When `start == n`, the chosen substrings cover the entire string from left to right, with no gaps and no overlap. Therefore, the current path is a valid palindrome partition.

Every valid partition can be described by its cut positions. During DFS, those cuts correspond to choosing the same sequence of `end` indices. Since the DFS tries every possible `end` at each `start`, it eventually constructs every valid partition.

Therefore, the algorithm returns exactly all palindrome partitions.

## Complexity

Let `n = len(s)`.

The palindrome table costs:

| Metric | Value |
|---|---:|
| Time | `O(n^2)` |
| Space | `O(n^2)` |

The number of partitions can be exponential. For a string like:

```python
"aaaaaaaaaaaaaaaa"
```

many substrings are palindromes, so many partitions are valid.

The full complexity is:

| Metric | Value | Why |
|---|---:|---|
| Time | `O(n * 2^n)` | There can be `2^(n-1)` partitions, and copying each path can cost up to `O(n)` |
| Space | `O(n^2)` | Palindrome table plus recursion path |

The output itself can also take `O(n * 2^n)` space.

## Implementation

```python
class Solution:
    def partition(self, s: str) -> list[list[str]]:
        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

        result = []
        path = []

        def dfs(start: int) -> None:
            if start == n:
                result.append(path[:])
                return

            for end in range(start, n):
                if not is_pal[start][end]:
                    continue

                path.append(s[start:end + 1])
                dfs(end + 1)
                path.pop()

        dfs(0)
        return result
```

## Code Explanation

We create a two-dimensional table:

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

Then we fill it from right to left by `start`:

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

This order matters because `is_pal[start][end]` may depend on:

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

So the inside substring must already be computed.

The check is:

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

If true, `s[start:end+1]` is a palindrome.

The backtracking path stores the current partition:

```python
path = []
```

When the whole string has been consumed:

```python
if start == n:
    result.append(path[:])
    return
```

We append a copy of `path`, not `path` itself, because `path` will continue changing during backtracking.

For each valid palindrome substring:

```python
path.append(s[start:end + 1])
dfs(end + 1)
path.pop()
```

The `append` makes a choice.

The recursive call solves the remaining suffix.

The `pop` undoes the choice so we can try another substring.

## Testing

```python
def normalize(ans: list[list[str]]) -> list[list[str]]:
    return sorted(ans)

def run_tests():
    s = Solution()

    assert normalize(s.partition("aab")) == normalize([
        ["a", "a", "b"],
        ["aa", "b"],
    ])

    assert s.partition("a") == [["a"]]

    assert normalize(s.partition("ab")) == normalize([
        ["a", "b"],
    ])

    assert normalize(s.partition("aaa")) == normalize([
        ["a", "a", "a"],
        ["a", "aa"],
        ["aa", "a"],
        ["aaa"],
    ])

    assert normalize(s.partition("efe")) == normalize([
        ["e", "f", "e"],
        ["efe"],
    ])

    print("all tests passed")

run_tests()
```

Test meaning:

| Test | Why |
|---|---|
| `"aab"` | Standard example with two partitions |
| `"a"` | Single-character base case |
| `"ab"` | No multi-character palindrome |
| `"aaa"` | Many valid cuts |
| `"efe"` | Odd-length palindrome |