Palindrome Partitioning
List every way to cut a string into palindromes with backtracking: cut a palindrome off the front, partition the rest, undo.
Problem Understanding
Palindrome Partitioning: split the string s so that every piece is a palindrome, and return every such partition.
Example: "aab" returns [["a", "a", "b"], ["aa", "b"]].
The Intuition: Choose the First Piece
Every partition starts with some piece s[0..end), and that piece must be a palindrome. Once it is cut off, what remains is the same problem on a shorter string.
Backtracking turns that into code with one shared path:
- If
startis the end of the string, the path is a full partition: record it. - Otherwise, for each
endafterstart, skips[start..end)unless it is a palindrome. - Append the palindrome, partition from
end, then pop it and try a longer piece.
The skipped pieces prune the tree: no partition can start with a piece that is not a palindrome.
Interactive Walkthrough
Pieces already cut into the path are shaded, with a gap after each one. The piece being tried is filled, or outlined in red when it is not a palindrome. Recorded partitions collect beside the string.
Dry Run Table
Input: "aab"
| First piece | Rest | Partitions of the rest | Result |
|---|---|---|---|
| a | ab | a, b | [a, a, b] |
| aa | b | b | [aa, b] |
| aab | — | not a palindrome | skipped |
Two partitions.
The Solution Template
Backtracking over the first piece: skip non-palindromes, choose, recurse, undo.
Palindrome Partitioning Code
1var partition = function(s) {2 const out = [], path = [];3 const isPal = (l, r) => {4 while (l < r) if (s[l++] !== s[r--]) return false;5 return true;6 };7 const backtrack = (start) => {8 if (start === s.length) {9 out.push([...path]);10 return;11 }12 for (let end = start + 1; end <= s.length; end++) {13 if (!isPal(start, end - 1)) continue;14 path.push(s.slice(start, end));15 backtrack(end);16 path.pop();17 }18 };19 backtrack(0);20 return out;21};
Edge Cases & Common Mistakes
- Recording the path itself: append a copy (
path[:],new ArrayList<>(path)), or every recorded partition changes as the path is undone. - Single letters: every single character is a palindrome, so at least one partition always exists.
- Off-by-one in the slice:
s[start:end]excludesend; the palindrome check must useend − 1as its right index. - Repeated checks: checking the same substring many times is wasteful on long strings; a DP palindrome table makes each check O(1).
Summary
Cut a palindromic first piece, partition the rest recursively, and undo to try a longer piece. Record the path when the whole string is cut. Non-palindromic pieces are skipped, which prunes the search. O(n · 2^n) time in the worst case.
More practice: DSA interview questions with answers · patterns cheat sheet