Palindrome Partitioning (LeetCode 131)
Given a string s, cut it into consecutive pieces so that every piece reads the same forwards and backwards (a palindrome). Return every distinct way to cut s this way.
Worked Examples
s = "aab"[["a","a","b"],["aa","b"]]"aa" is a palindrome, so it may stay together; "aab" and "ab" are not, so no other cut works.s = "a"[["a"]]⚖️Formal Constraints & Bounds
1 <= s.length <= 16scontains only lowercase English letters.
Core Insight
Validating the prefix constraint before recursive descent eliminates entire subtrees of invalid work.
Real-World Scenario & Production Applications
Genomic DNA sequence symmetric motif segmentation, computational linguistics palindrome tokenization.
Subproblems & Recurrence Decomposition3 Phases
Check if substring s[start:end+1] is a palindrome before branching further.
for end in range(start, len(s)):
if is_palindrome(s, start, end):Step-by-Step Execution Trace Table
[ "aab" ] (Root, start=0, d=0) / | \ cut 'a' (0:1) / cut 'aa' | cut 'aab' \ (0:3, not palindrome) / (0:2) | \ [ "a" ] (d=1) [ "aa" ] (d=1) ✂️ PRUNED ("aab" not pal) / \ | cut 'a' / \ cut 'ab' | cut 'b' (2:3) (1:2) / \ (1:3 not) | [ "a", "a" ] ✂️ PRUNED [ "aa", "b" ] ✅ (start=3, d=2, Base Case hit!) | (d=2) cut 'b'| (2:3) | [ "a", "a", "b" ] ✅ (start=3, d=3, Base Case hit!) Step-by-Step Decision Trace
- Step 1 (Root, d=0): Suffix
"aab". Test prefix cuts fromstart=0:'a','aa','aab'. - Step 2 (Choose 'a', d=1):
'a'is a palindrome ✅path = ['a']. Recurse withstart=1. - Step 3 (Choose 'a', d=2):
'a'is a palindrome ✅path = ['a', 'a']. Recurse withstart=2. - Step 4 (Choose 'b', d=3):
'b'is a palindrome ✅path = ['a', 'a', 'b']. Base Case (start == 3): Record['a', 'a', 'b']✅. - Step 5 (Backtrack / Pop 'b', d=2):
path = ['a', 'a']. Loop atstart=2exhausted. - Step 6 (Backtrack / Pop 'a', d=1):
path = ['a']. Next cut atstart=1is'ab'(1:3). - Step 7 (Cut 'ab', d=2):
'ab'is NOT a palindrome ❌ ✂️ PRUNE branch (no recursive calls). - Step 8 (Backtrack / Pop 'a', d=0):
path = []. Next root cut is'aa'(0:2). - Step 9 (Choose 'aa', d=1):
'aa'is a palindrome ✅path = ['aa']. Recurse withstart=2. - Step 10 (Choose 'b', d=2):
'b'is a palindrome ✅path = ['aa', 'b']. Base Case (start == 3): Record['aa', 'b']✅. - Step 11 (Backtrack / Pop 'b', d=1):
path = ['aa']. - Step 12 (Backtrack / Pop 'aa', d=0):
path = []. Next root cut is'aab'(0:3). - Step 13 (Cut 'aab', d=1):
'aab'is NOT a palindrome ❌ ✂️ PRUNE branch. Output:[['a', 'a', 'b'], ['aa', 'b']].
s = "aab"Expected:[["a","a","b"],["aa","b"]]| 1 | results, path = [], [] |
| 2 | def is_palindrome(low, high): |
| 3 | compare s[low] with s[high], moving both pointers inward |
| 4 | def backtrack(start): |
| 5 | if start == len(s): |
| 6 | results.append(list(path)) |
| 7 | return |
| 8 | for end in range(start, len(s)): |
| 9 | if is_palindrome(start, end): |
| 10 | path.append(s[start:end + 1]) |
| 11 | backtrack(end + 1) |
| 12 | path.pop() |
| 13 | backtrack(0) |
| 14 | return results |
Conceptual Narrative
🧭 Conceptual Foundation & Pattern Intuition
Palindrome Partitioning asks us to slice a string into contiguous substrings such that every substring in the partition is a palindrome. This is a classic prefix-slicing decision tree: at any index start, we try every last index end of the next piece, from start to len(s) - 1. The crucial insight is early branch pruning: if the piece s[start:end + 1] is not a palindrome, we do not bother recursing on the remaining suffix! That branch dies immediately, saving exponential wasted computation.
🏟️ The Analogy: Cutting Bamboo into Symmetrical Segments
Imagine you are a craftsman cutting a long pole of patterned bamboo into sections. The client's strict rule is: "Every single piece cut from the pole must have a symmetrical pattern (a palindrome)." You position your saw at the first notch and inspect the candidate piece. If it isn't symmetrical, you don't cut—you slide the saw to the next notch. When you find a cut that produces a symmetrical section, you saw it off, set it aside, and hand the remaining pole to your apprentice to repeat the process. If the apprentice runs out of pole with valid pieces, the whole set is accepted.
🔑 Why It Works
Notice how backtrack(end + 1) starts the next piece right after the last index of this one. When start == len(s), we know with mathematical certainty that every piece currently in path is a valid palindrome that together reassembles into the original string.
Re-checking palindrome property in repeatedly: Calling
s[start:end] == s[start:end][::-1]inside the loop takes per partition candidate. Precomputing a 2D boolean palindrome tableis_pal[i][j]accelerates checks to .Substring slicing off-by-one: In Python, slicing substring from
starttoendinclusive requiress[start : end + 1]. Forgetting+1drops the last character.Base case condition off-by-one: The base case is reached when
start == len(s), meaning all characters have been successfully partitioned into valid palindromes.
4-Phase Thought Process Model
Pattern Recognition Signals
The 10-second spot
The Signal: You are asked to 'partition' a string into contiguous chunks, every chunk must satisfy a specific rule (e.g., being a palindrome), and you need all possible combinations.
The Translation: 'Find all combinations' + 'contiguous chunks' + 'specific rule' = Backtracking with Branch Pruning.
Formulating the Predicate & Invariants
Turning intuition into a boolean rule
The Invariant: Every segment inside your current path array is already a confirmed palindrome.
The State (start): Your start/index variable always marks the exact boundary of the remaining string suffix you still need to partition.
Silent Failure Traps & Edge Cases
Where confident candidates still lose points
Pruning Too Late: The biggest trap in this problem is recursing before checking if the current prefix is a palindrome. You must check
is_palindrome(start, end)first. If false, stop immediately (prune the branch) to avoid exponential 2^N wasted work.Saving Too Early: save
pathonly whenstart == len(s). Saving on every call also returns splits that leave the end ofsunused, such as["a"]and["a", "a"]for"aab".
The 60-Second Interview Pitch
Say this out loud before you type a single line
"I'd use String Partitioning. Every split of the string is a first piece followed by a split of the rest, so backtrack(start) tries every end from start to the last index. When is_palindrome(start, end) holds, I append s[start:end + 1] to path, recurse on end + 1, and pop the piece when I come back. Each split has exactly one first piece, so trying every end in turn builds every split once and never twice. The trap is where I save: only when start equals len(s), because only then has every character been placed in a piece. If I saved on every call, for 'aab' I would also return partial splits such as ['a'] and ['a', 'a']. When I save, I append a copy of path, since path keeps changing. There can be up to 2^N splits, each built in
O(N), so it's O(N times 2^N) time, withO(N)recursion stack."
Complexity & Mathematical Proof
O(N · 2^N)
There are N - 1 potential cut positions in string of length N (2^(N-1) partition combinations). For each valid partition, palindrome check takes O(N) time.
O(N) Call Stack
Recursion stack depth <= N; path array of substrings.
T(N) = 2^{N-1} · O(N) = O(N · 2^N)
Derivation Progression
2^{N-1} possible partitions
At each between-character boundary, choice is to cut or keep extending.
O(N) prefix check
Validates candidate substring is a palindrome before recursing.
O(N · 2^N)
Worst case when all characters are identical (e.g. 'aaaa').
Variable Definitions
Length of the input string
Memory Architecture & Bounds
O(N) Call stack frames
O(N) Current partition path array
O(N · 2^N) List of partition lists
Boundary Best / Worst Cases
when all letters differ: only one split exists, but every end is still tried at every start.
.
for all-identical string.
Decision & State-Space Search Tree
Senior SWE Deconstruction & Hardware Caveats
Triggers: "partition string such that every substring is a palindrome". Branch pruning with early constraint verification: do NOT generate all partitions and check palindromes at the end! Prune recursive exploration immediately if prefix is not a palindrome.
. At len(s) = 16 there can be splits (all letters equal), so the output, not the search, sets the cost.
Verify palindrome via two pointers s[l] == s[r] or precomputed 2D boolean DP.
Palindrome Partitioning (LeetCode 131)
Given a string s, cut it into consecutive pieces so that every piece reads the same forwards and backwards (a palindrome). Return every distinct way to cut s this way.
Worked Examples
s = "aab"[["a","a","b"],["aa","b"]]"aa" is a palindrome, so it may stay together; "aab" and "ab" are not, so no other cut works.s = "a"[["a"]]⚖️Formal Constraints & Bounds
1 <= s.length <= 16scontains only lowercase English letters.
Core Insight
Validating the prefix constraint before recursive descent eliminates entire subtrees of invalid work.
Real-World Scenario & Production Applications
Genomic DNA sequence symmetric motif segmentation, computational linguistics palindrome tokenization.
Subproblems & Recurrence Decomposition3 Phases
Check if substring s[start:end+1] is a palindrome before branching further.
for end in range(start, len(s)):
if is_palindrome(s, start, end):Step-by-Step Execution Trace Table
[ "aab" ] (Root, start=0, d=0) / | \ cut 'a' (0:1) / cut 'aa' | cut 'aab' \ (0:3, not palindrome) / (0:2) | \ [ "a" ] (d=1) [ "aa" ] (d=1) ✂️ PRUNED ("aab" not pal) / \ | cut 'a' / \ cut 'ab' | cut 'b' (2:3) (1:2) / \ (1:3 not) | [ "a", "a" ] ✂️ PRUNED [ "aa", "b" ] ✅ (start=3, d=2, Base Case hit!) | (d=2) cut 'b'| (2:3) | [ "a", "a", "b" ] ✅ (start=3, d=3, Base Case hit!) Step-by-Step Decision Trace
- Step 1 (Root, d=0): Suffix
"aab". Test prefix cuts fromstart=0:'a','aa','aab'. - Step 2 (Choose 'a', d=1):
'a'is a palindrome ✅path = ['a']. Recurse withstart=1. - Step 3 (Choose 'a', d=2):
'a'is a palindrome ✅path = ['a', 'a']. Recurse withstart=2. - Step 4 (Choose 'b', d=3):
'b'is a palindrome ✅path = ['a', 'a', 'b']. Base Case (start == 3): Record['a', 'a', 'b']✅. - Step 5 (Backtrack / Pop 'b', d=2):
path = ['a', 'a']. Loop atstart=2exhausted. - Step 6 (Backtrack / Pop 'a', d=1):
path = ['a']. Next cut atstart=1is'ab'(1:3). - Step 7 (Cut 'ab', d=2):
'ab'is NOT a palindrome ❌ ✂️ PRUNE branch (no recursive calls). - Step 8 (Backtrack / Pop 'a', d=0):
path = []. Next root cut is'aa'(0:2). - Step 9 (Choose 'aa', d=1):
'aa'is a palindrome ✅path = ['aa']. Recurse withstart=2. - Step 10 (Choose 'b', d=2):
'b'is a palindrome ✅path = ['aa', 'b']. Base Case (start == 3): Record['aa', 'b']✅. - Step 11 (Backtrack / Pop 'b', d=1):
path = ['aa']. - Step 12 (Backtrack / Pop 'aa', d=0):
path = []. Next root cut is'aab'(0:3). - Step 13 (Cut 'aab', d=1):
'aab'is NOT a palindrome ❌ ✂️ PRUNE branch. Output:[['a', 'a', 'b'], ['aa', 'b']].
s = "aab"Expected:[["a","a","b"],["aa","b"]]| 1 | results, path = [], [] |
| 2 | def is_palindrome(low, high): |
| 3 | compare s[low] with s[high], moving both pointers inward |
| 4 | def backtrack(start): |
| 5 | if start == len(s): |
| 6 | results.append(list(path)) |
| 7 | return |
| 8 | for end in range(start, len(s)): |
| 9 | if is_palindrome(start, end): |
| 10 | path.append(s[start:end + 1]) |
| 11 | backtrack(end + 1) |
| 12 | path.pop() |
| 13 | backtrack(0) |
| 14 | return results |
Conceptual Narrative
🧭 Conceptual Foundation & Pattern Intuition
Palindrome Partitioning asks us to slice a string into contiguous substrings such that every substring in the partition is a palindrome. This is a classic prefix-slicing decision tree: at any index start, we try every last index end of the next piece, from start to len(s) - 1. The crucial insight is early branch pruning: if the piece s[start:end + 1] is not a palindrome, we do not bother recursing on the remaining suffix! That branch dies immediately, saving exponential wasted computation.
🏟️ The Analogy: Cutting Bamboo into Symmetrical Segments
Imagine you are a craftsman cutting a long pole of patterned bamboo into sections. The client's strict rule is: "Every single piece cut from the pole must have a symmetrical pattern (a palindrome)." You position your saw at the first notch and inspect the candidate piece. If it isn't symmetrical, you don't cut—you slide the saw to the next notch. When you find a cut that produces a symmetrical section, you saw it off, set it aside, and hand the remaining pole to your apprentice to repeat the process. If the apprentice runs out of pole with valid pieces, the whole set is accepted.
🔑 Why It Works
Notice how backtrack(end + 1) starts the next piece right after the last index of this one. When start == len(s), we know with mathematical certainty that every piece currently in path is a valid palindrome that together reassembles into the original string.
Re-checking palindrome property in repeatedly: Calling
s[start:end] == s[start:end][::-1]inside the loop takes per partition candidate. Precomputing a 2D boolean palindrome tableis_pal[i][j]accelerates checks to .Substring slicing off-by-one: In Python, slicing substring from
starttoendinclusive requiress[start : end + 1]. Forgetting+1drops the last character.Base case condition off-by-one: The base case is reached when
start == len(s), meaning all characters have been successfully partitioned into valid palindromes.
4-Phase Thought Process Model
Pattern Recognition Signals
The 10-second spot
The Signal: You are asked to 'partition' a string into contiguous chunks, every chunk must satisfy a specific rule (e.g., being a palindrome), and you need all possible combinations.
The Translation: 'Find all combinations' + 'contiguous chunks' + 'specific rule' = Backtracking with Branch Pruning.
Formulating the Predicate & Invariants
Turning intuition into a boolean rule
The Invariant: Every segment inside your current path array is already a confirmed palindrome.
The State (start): Your start/index variable always marks the exact boundary of the remaining string suffix you still need to partition.
Silent Failure Traps & Edge Cases
Where confident candidates still lose points
Pruning Too Late: The biggest trap in this problem is recursing before checking if the current prefix is a palindrome. You must check
is_palindrome(start, end)first. If false, stop immediately (prune the branch) to avoid exponential 2^N wasted work.Saving Too Early: save
pathonly whenstart == len(s). Saving on every call also returns splits that leave the end ofsunused, such as["a"]and["a", "a"]for"aab".
The 60-Second Interview Pitch
Say this out loud before you type a single line
"I'd use String Partitioning. Every split of the string is a first piece followed by a split of the rest, so backtrack(start) tries every end from start to the last index. When is_palindrome(start, end) holds, I append s[start:end + 1] to path, recurse on end + 1, and pop the piece when I come back. Each split has exactly one first piece, so trying every end in turn builds every split once and never twice. The trap is where I save: only when start equals len(s), because only then has every character been placed in a piece. If I saved on every call, for 'aab' I would also return partial splits such as ['a'] and ['a', 'a']. When I save, I append a copy of path, since path keeps changing. There can be up to 2^N splits, each built in
O(N), so it's O(N times 2^N) time, withO(N)recursion stack."
Complexity & Mathematical Proof
O(N · 2^N)
There are N - 1 potential cut positions in string of length N (2^(N-1) partition combinations). For each valid partition, palindrome check takes O(N) time.
O(N) Call Stack
Recursion stack depth <= N; path array of substrings.
T(N) = 2^{N-1} · O(N) = O(N · 2^N)
Derivation Progression
2^{N-1} possible partitions
At each between-character boundary, choice is to cut or keep extending.
O(N) prefix check
Validates candidate substring is a palindrome before recursing.
O(N · 2^N)
Worst case when all characters are identical (e.g. 'aaaa').
Variable Definitions
Length of the input string
Memory Architecture & Bounds
O(N) Call stack frames
O(N) Current partition path array
O(N · 2^N) List of partition lists
Boundary Best / Worst Cases
when all letters differ: only one split exists, but every end is still tried at every start.
.
for all-identical string.
Decision & State-Space Search Tree
Senior SWE Deconstruction & Hardware Caveats
Triggers: "partition string such that every substring is a palindrome". Branch pruning with early constraint verification: do NOT generate all partitions and check palindromes at the end! Prune recursive exploration immediately if prefix is not a palindrome.
. At len(s) = 16 there can be splits (all letters equal), so the output, not the search, sets the cost.
Verify palindrome via two pointers s[l] == s[r] or precomputed 2D boolean DP.