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:

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

s = "aab"

Possible partitions:

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

Both are valid because every substring is a palindrome.

Output:

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

Example 2:

s = "a"

The only partition is:

["a"]

Output:

[["a"]]

Input and Output

Function shape:

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:

a a b

There are two gaps:

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:

s = "aab"

At start = 0, possible next substrings are:

"a"
"aa"
"aab"

Only "a" and "aa" are palindromes.

So we try:

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:

is_pal[i][j]

meaning:

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:

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:

Algorithm

Let n = len(s).

First, build the palindrome table.

Then run DFS:

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:

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

"aaaaaaaaaaaaaaaa"

many substrings are palindromes, so many partitions are valid.

The full complexity is:

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

Implementation

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:

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

Then we fill it from right to left by start:

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

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

is_pal[start + 1][end - 1]

So the inside substring must already be computed.

The check is:

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:

path = []

When the whole string has been consumed:

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:

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

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: