Appearance
4.18.7 — Palindrome Partitioning
LeetCode 131 · Medium · ★ Blind 75
The problem
Cut the string into pieces so that every piece is a palindrome. Return all possible ways.
"aab" → [["a","a","b"], ["aa","b"]]The string is at most 16 characters.
The pattern
The choices here are not elements — they are cut positions.
Standing at index start, the piece you take next can end anywhere from start to the end of the string. Each ending is one branch. Take the piece only if it is a palindrome, recurse from just after it, then undo.
"aab", starting at 0:
take "a" → recurse from 1
take "a" → recurse from 2
take "b" → recurse from 3 = end → record ["a","a","b"] ✓
take "ab" → not a palindrome, rejected
take "aa" → recurse from 2
take "b" → end → record ["aa","b"] ✓
take "aab" → not a palindrome, rejectedThis is the same start-index loop as 4.18.1 Subsets. Only the meaning of the loop variable changed: it is a cut point rather than an item index.
Recognising that is the point of the problem. When you can phrase the choices as "what do I take next, and where does it end", the template is unchanged.
The solution
python
class Solution:
def partition(self, s: str) -> List[List[str]]:
result = []
path = []
def is_palindrome(lo: int, hi: int) -> bool:
while lo < hi:
if s[lo] != s[hi]:
return False
lo += 1
hi -= 1
return True
def backtrack(start: int):
if start == len(s): # consumed the whole string
result.append(path[:])
return
for end in range(start, len(s)): # the piece is s[start..end]
if not is_palindrome(start, end):
continue # prune: not a valid piece
path.append(s[start:end + 1])
backtrack(end + 1) # continue after this piece
path.pop()
backtrack(0)
return resultts
function partition(s: string): string[][] {
const result: string[][] = [];
const path: string[] = [];
function isPal(lo: number, hi: number): boolean {
while (lo < hi) {
if (s[lo] !== s[hi]) return false;
lo++; hi--;
}
return true;
}
function backtrack(start: number): void {
if (start === s.length) {
result.push([...path]);
return;
}
for (let end = start; end < s.length; end++) {
if (!isPal(start, end)) continue;
path.push(s.slice(start, end + 1));
backtrack(end + 1);
path.pop();
}
}
backtrack(0);
return result;
}The palindrome check is the pruning, and it happens before recursing. That is what stops the search exploring every one of the 2^{n-1} possible cuttings — most branches die at the check.
is_palindrome takes indices, not a substring. Passing s[start:end+1] would allocate a new string on every check, which is O(n) of pure waste per call. Comparing in place with two pointers is the same discipline as 4.2 and 4.5.1.
backtrack(end + 1) — the next piece starts immediately after the one just taken.
The base case is start == len(s), meaning the whole string has been consumed. There is no leftover to worry about, because every branch takes a piece and moves past it.
Precomputing the palindromes
The palindrome check costs O(n) and is called from every node of the tree, and many of those checks repeat. You can compute all of them once, in O(n^2), with a small dynamic program:
python
n = len(s)
pal = [[False] * n for _ in range(n)]
for hi in range(n):
for lo in range(hi, -1, -1):
if s[lo] == s[hi] and (hi - lo < 2 or pal[lo + 1][hi - 1]):
pal[lo][hi] = TrueRead the condition: s[lo..hi] is a palindrome when its two ends match and the inside is already known to be one. hi - lo < 2 covers the pieces of length 1 and 2, which have no inside.
The loop order matters — lo counts downwards so that pal[lo+1][hi-1] is already filled when it is needed. That "fill the table in an order where the dependencies already exist" idea is the core of 4.24.
With the table, is_palindrome(lo, hi) becomes an O(1) lookup and the whole search drops a factor of n. Say this even if you do not write it — recognising the repeated work is the observation being tested.
Complexity
O(2^{n-1} \times n) in the worst case. A string of n characters has n−1 gaps and each is either cut or not, so there are 2^{n-1} possible partitions; copying each result costs O(n).
The worst case is a string like "aaaa", where every piece is a palindrome and nothing is ever pruned. On ordinary strings the pruning removes almost everything.
O(n) space for the recursion, or O(n^2) with the precomputed table.
Where this goes next
- Palindrome Partitioning II — the minimum number of cuts. Enumerating every partition and taking the smallest is far too slow. Because you only need an optimum rather than every answer, it becomes DP: O(n^2). 4.23.
- Word Break II — cut a string into dictionary words and return all of them. Identical template with the dictionary check replacing the palindrome check.
- Restore IP Addresses — cut a digit string into four valid octets. Same template, with a validity check and a piece-count limit.
The recurring dividing line: all the answers means backtracking; the best answer or how many means DP. Combination Sum II and Combination Sum IV sit on either side of it, and so do these two Palindrome Partitioning problems.
What the interviewer will push on
"What are the choices at each step?" Where the next piece ends.
"Where is the pruning?" The palindrome check before recursing.
"Why pass indices instead of substrings to the checker?" Slicing allocates and costs O(n) per check.
"Can you avoid re-checking the same substrings?" Precompute an n \times n table in O(n^2).
"What if you only needed the minimum number of cuts?" DP, not backtracking, and say why: you want one optimum, not every arrangement.
One thing to volunteer: point out that this is the subsets template where the loop variable is a cut position. Naming the reused skeleton is worth more than the code.
Next: 4.18.8 Letter Combinations of a Phone Number — the simplest possible branching, driven by a lookup table.