The problem
Split a string into pieces so that every piece is a palindrome. Return every possible way to do it.
Input: "aab" Output: [["a","a","b"], ["aa","b"]]
Picture it
Picture a ribbon of letters and a pair of scissors. You make your first cut somewhere, but only if the piece you cut off reads the same backwards (a mirror piece). Then you cut the rest the same way. Each complete set of cuts is one answer.
How to recognise it
- You must split a sequence into consecutive pieces, and every piece must satisfy a rule (here, reading the same forwards and backwards).
- The answer is all valid splits, not one or a count.
- The input is very short (at most 16 letters), which allows exponential work: there are 2^15 = 32,768 ways to cut 16 letters.
- Each decision is "where does the next piece end?", and a bad piece means you can abandon that whole branch at once.
- Choosing a piece, recursing on what is left, and undoing the choice is backtracking over cut positions.
Start with brute force
Every way to cut a string of n letters is a choice for each of the n − 1 gaps: cut or not. Try every combination of gap choices, build the pieces, and keep the splits where all pieces are palindromes.
def partition_brute(s):
n = len(s)
out = []
for mask in range(1 << (n - 1)):
cuts = [i + 1 for i in range(n - 1) if mask >> i & 1]
pieces = [s[a:b] for a, b in zip([0] + cuts, cuts + [n])]
if all(p == p[::-1] for p in pieces):
out.append(pieces)
return out
For n = 16 that is 32,768 cut sets, each building up to 16 pieces and testing them. That is small at this limit, but it builds all the cut sets for "abcdefghijklmnop" (one valid split) just as it does for "aaaaaaaaaaaaaaaa" (32,768 valid splits). Time is O(n · 2^n), and space is O(n) per candidate beyond the output.
From brute force to the idea
- Find the waste. In
"abcd..."the brute force builds splits such as["abc", "d", ...]even though the first piece"abc"already fails. It tests the pieces only at the end. - Build the split piece by piece.
cut(start)means "the string beforestartis already split into good pieces; now split the rest". - Try every end position. For
endfromstart + 1tolen(s), takepiece = s[start:end]. - Recurse only on palindromes. If
piece == piece[::-1], append it topartsand callcut(end). Otherwise do nothing: that cut position is dead. - Undo. After the recursive call,
parts.pop()removes the piece so the next end position starts clean. - Save at the end. When
start == len(s)the whole string is covered, so store a copy ofparts.
This is the key idea: extend the split one palindrome at a time and abandon any bad piece immediately. The palindrome test slices and reverses, which costs O(length of the piece).
The key idea
Backtracking: try every end position for the next piece, recurse only if that piece is a palindrome.
Python solution
def partition(s):
out, parts = [], []
def cut(start):
if start == len(s):
out.append(parts[:])
return
for end in range(start + 1, len(s) + 1):
piece = s[start:end]
if piece == piece[::-1]:
parts.append(piece)
cut(end)
parts.pop()
cut(0)
return outIn the interactive version each line lights up as the animation runs, and you can type your own input to see the algorithm handle it.
Complexity
| Approach | Time | Space |
|---|---|---|
| Brute force (all 2^(n−1) cut sets) | O(n · 2^n): every cut set builds and tests its pieces | O(n) per candidate, plus the output |
| Pruned backtracking (shown code) | O(n · 2^n) in the worst case (all letters equal, every split valid), far less on strings with few palindromes | O(n) beyond the output: recursion depth and parts |
On "abcdefghijklmnop" the shown code tests only 136 pieces in total (16 + 15 + ... + 1, because every one-letter piece passes and nothing longer does), against 32,768 cut sets for the brute force. On "aaaaaaaaaaaaaaaa" it tests 65,535 pieces, because every split works.
Edge cases
- One letter (
"a"): returns[["a"]]. - No palindromes longer than one letter (
"ab"): returns[["a", "b"]]. The result is never empty, because the split into single letters is always valid. - All equal (
"aaa"): returns four splits:[a, a, a],[a, aa],[aa, a]and[aaa]. - Example (
"aab"): returns[["a", "a", "b"], ["aa", "b"]]. - Empty string: returns
[[]], one split with no pieces. The problem guarantees at least one letter. - Recursion depth is at most n + 1 = 17, far below Python's limit.
Common mistakes
- Starting the inner loop at
range(start, ...), so the first piece is the empty string. The empty string equals its reverse,cut(start)calls itself with no progress, and Python raisesRecursionErroron"aab". - Appending
partsinstead ofparts[:], so every saved answer is the same list, empty at the end. - Testing only whether the whole string is a palindrome rather than each piece.
- Forgetting
parts.pop(), so pieces from a dead branch stay in the next answer.
Return only the splits in which every piece has at least 2 letters and is a palindrome. For "aabb" the answer is [["aa", "bb"]], and for "aab" it is empty. Describe the change, then write it if you like.
Compare with our answer
The structure stays the same; add the length rule to the test that guards the recursive call. A piece that is too short is treated like a non-palindrome, so the branch is dropped.
def partition_min2(s):
out, parts = [], []
def cut(start):
if start == len(s):
out.append(parts[:])
return
for end in range(start + 1, len(s) + 1):
piece = s[start:end]
if len(piece) >= 2 and piece == piece[::-1]:
parts.append(piece)
cut(end)
parts.pop()
cut(0)
return out
The worst case is still O(n · 2^n), but fewer branches survive. The result can be empty (for "aab"), which is why the answer must be allowed to have no lists at all.
A strong answer mentions: adding the length condition to the guard, that the answer may now be empty, and a test such as "aab".
1. A text editor must list every way to break a 14-letter code into consecutive chunks that each read the same backwards and forwards. Which approach fits best?
The task is to list every valid split, and the chunks depend on each other, so you extend the split chunk by chunk and drop a branch as soon as a chunk fails. A single reverse test, sorting, or one cut position cannot enumerate the splits.
2. For "aaaaaaaaaaaaaaaa" (16 letters) the shown code is still O(n · 2^n). Why?
Pruning only helps when some piece fails. When all letters are equal, every cut gives a palindrome, so all 32,768 splits are produced and copied. The recursion depth is at most n + 1.
3. A learner changes range(start + 1, len(s) + 1) to range(start, len(s) + 1). What happens for "aab"?
With end == start the piece is "", which equals its reverse, so the code appends it and calls cut(start) again with no progress. The recursion never ends, so the extra splits are never returned.
Score 60% or more and the lesson is marked complete.