Example 1
ready- Input
s = "aab"- Expected
[ [ "a", "a", "b" ], [ "aa", "b" ] ]- Why
- both single a's and the combined aa are palindromes
Palindrome Partitioning
35 min · partition()mediumOpen in LeetCode #131 ↗
A string can tell several different mirror-stories depending on where you cut it.
aab, for instance, has useful cuts after either the first or second a.
A palindrome is text that reads the same from left to right and right to left. Split
the lowercase string s into non-empty pieces so every piece is a palindrome. Return
every valid splitting.
Each result is an ordered list of pieces: joining that list must recreate s exactly.
The collection of results itself may come back in any order.
Constraints
1 <= s.length <= 12scontains lowercase English letters only.- No input produces more than 2,048 partitionings.
Hints
Cuts are choices too
A string of length n has n - 1 gaps between characters. Each gap is either cut
or uncut, so you can enumerate every cut pattern and filter the bad ones.
Choose the next piece
From a starting index, try every possible ending index. Recurse only when
s[start:end + 1] is a palindrome.
Undo the piece
Add a palindromic prefix to the current partition, search from the next unread character, then remove that piece. Reaching the end means the current list is one complete answer.
Follow-up
Could you precompute which substrings are palindromes so the search never scans the same substring twice?
Visible cases
Examples
Example 2
ready- Input
s = "a"- Expected
[ [ "a" ] ]- Why
- one character is already a palindrome
Example 3
ready- Input
s = "abc"- Expected
[ [ "a", "b", "c" ] ]- Why
- no multi-character piece is palindromic
Interview signal
Asked at
AmazonGoogle
Enumerate every cut set
There are n - 1 gaps between neighboring characters. A bit mask can choose which gaps
receive cuts, giving 2^(n - 1) candidate partitionings. Build each candidate, then
keep it only if every piece equals its reverse.
def partition(s: str) -> list[list[str]]:
result: list[list[str]] = []
gap_count = len(s) - 1
for mask in range(1 << gap_count):
pieces: list[str] = []
start = 0
for gap in range(gap_count):
if mask & (1 << gap):
pieces.append(s[start:gap + 1])
start = gap + 1
pieces.append(s[start:])
if all(piece == piece[::-1] for piece in pieces):
result.append(pieces)
return resultBuilding and checking one candidate touches O(n) characters. Time O(2ⁿ · n). Space O(n) auxiliary for one candidate, excluding the returned partitionings.
Palindrome-prefix backtracking
This is the backtracking pattern: choose one valid next piece, explore the remaining suffix, then remove that piece. Unlike cut-set enumeration, it abandons a candidate the moment its next piece isn't palindromic.
def partition(s: str) -> list[list[str]]:
result: list[list[str]] = []
path: list[str] = []
def is_palindrome(left: int, right: int) -> bool:
while left < right:
if s[left] != s[right]:
return False
left += 1
right -= 1
return True
def search(start: int) -> None:
if start == len(s):
result.append(path.copy())
return
for end in range(start, len(s)):
if not is_palindrome(start, end):
continue
path.append(s[start:end + 1])
search(end + 1)
path.pop()
search(0)
return resultThere can be 2^(n - 1) answers—an all-equal string reaches that bound—and each answer
contains O(n) characters. Time O(2ⁿ · n) in the worst case. Space O(n) auxiliary
for the path and call stack, excluding output.
The correctness argument follows the unread suffix. Every recursive step takes a palindromic prefix of that suffix; reaching its end gives valid pieces whose order and concatenation are already guaranteed.
Loading editor
Console
ready to runReady to run.
3 cases are queued.
Visible testcase
Case 1
Expected
[
[
"a",
"a",
"b"
],
[
"aa",
"b"
]
]Run: visible + custom · Submit: full suite