131. Palindrome Partitioning

131

MediumBacktrackingBacktracking (DFS over cut positions)Partition backtracking with palindrome check

Palindrome Partitioning

Given a string s, partition it so that every contiguous substring in the partition is a palindrome. Return all possible palindrome partitionings of s.

Open official problem prompt ↗

In plain English

Enumerate every way to slice the string into contiguous chunks such that each chunk reads the same forwards and backwards.

Picture it like this

Like cutting a ribbon printed with letters into pieces, but you are only allowed to keep a cut set where every piece is a symmetric word; you try each possible cut and undo it if the rest cannot be completed.

Example

Input: s = "aab"
Output: [["a","a","b"],["aa","b"]]
Why: Cutting after each 'a' gives palindromes a, a, b; cutting after 'aa' gives palindromes aa, b. No other cut set is fully palindromic.

Constraints

1 <= s.length <= 16s consists of lowercase English letters only

Pattern lesson

See the pattern, then code

Partition backtracking with palindrome check

↗

Backtracking

Generate every valid combination, permutation, partition, or configuration.. At each position, try every prefix as the next piece; only recurse when that prefix is a palindrome, so invalid branches are pruned immediately.

New words, made simpleKnow these before the algorithm

Partition: A division of the string into consecutive non-overlapping substrings that together cover the whole string.
Palindrome: A string equal to its own reverse, e.g. 'aa' or 'aba'.
Backtracking: Building a candidate incrementally and abandoning (undoing) it as soon as it cannot lead to a valid solution.

Approaches from first idea to best ideaCompare the trade-offs

ApproachHow it thinksCost

Generate all partitions, then filter

Wastes work exploring cut sets doomed by an early non-palindrome piece.

Produce every one of the 2^(n-1) cut combinations and keep those where all pieces are palindromes.

Time O(n * 2^n)Space O(n * 2^n)

Best choiceBacktracking with palindrome pruning

Same worst-case bound but prunes aggressively and uses only O(n) recursion/path space.

Only extend a branch when the current prefix is a palindrome, cutting off invalid subtrees at their root.

Time O(n * 2^n)Space O(n)

The rule we keep true

Invariant

Every substring already placed in path is a palindrome and they concatenate exactly to s[0:start].

Why this is correct

Reasoning

Because we recurse only on palindromic prefixes and cover indices start..end contiguously, any path that reaches start == len(s) is a complete cover of s by palindromes, and the loop over all end values guarantees no valid partition is missed.

The algorithm in three movesSay these aloud before coding

1From index start, extend an end pointer to form each candidate substring s[start:end]

start=0: take 'a' (palindrome) -> recurse at 1

2If that substring is a palindrome, add it to the current path

start=1: take 'a' -> recurse at 2, take 'b' -> record [a,a,b]

3Recurse from end to partition the remainder

back at start=0: take 'aa' -> recurse at 2 -> record [aa,b]

4When start reaches len(s), record a copy of the path

5Pop the last piece to backtrack and try a longer prefix

Visual trace

Follow the data, one decision at a time

Input snapshotHighlighted cells are involved in this example

1 · Readstart=0, prefix 'a'

2 · AskIs 'a' a palindrome?

3 · Update statepath=['a']

4 · ResultYes; recurse at index 1

Key takeaway

The string aab; the first two cells show single-character palindrome cuts being explored first.

Code walkthrough

Read the solution in small chunks

Python 3

Do not memorize the whole program. Connect each group of lines to one job in the algorithm.

1
Lines 6-9Base case
When start reaches the end, the path fully covers s with palindromes, so store a copy.
2
Lines 10-12Try every prefix
Extend end over each candidate substring and test whether it reads the same reversed.
3
Lines 13-16Choose, recurse, undo
Push the palindrome, recurse on the remainder, then pop to explore a longer prefix.

Make it stick

Edge cases, mistakes, and one self-check

Edge cases to test

Single character string returns [[c]]
String of identical characters like 'aaa' yields many partitions
Whole string already a palindrome adds the single-piece partition too

Common beginner mistakes

Appending path directly instead of path[:] so later mutations corrupt stored answers
Using range(start+1, len(s)) and missing the final substring
Recomputing palindrome checks without pruning, or checking on the full remainder instead of the current prefix

Check your understanding

Why do we recurse from end rather than from start+1 after taking a piece?

PyPython 3 · solution.py

Optimal

1class Solution:2    def partition(self, s: str) -> list[list[str]]:3        res: list[list[str]] = []4        path: list[str] = []56        def backtrack(start: int) -> None:7            if start == len(s):8                res.append(path[:])9                return10            for end in range(start + 1, len(s) + 1):11                sub = s[start:end]12                if sub == sub[::-1]:13                    path.append(sub)14                    backtrack(end)15                    path.pop()1617        backtrack(0)18        return res

Time complexityO(n * 2^n)Optimized

Space complexityO(n)Explained

Interview rehearsal

Explain before you code

25:00

Restate constraints and edge cases
Explain brute force and its bottleneck
State the invariant and complexity

Seen at

AmazonGoogleMicrosoft

Palindrome Partitioning

Palindrome Partitioning

See the pattern, then code

Invariant

Reasoning

Follow the data, one decision at a time

Read the solution in small chunks

Edge cases, mistakes, and one self-check

Edge cases to test

Common beginner mistakes

More in Backtracking