131. Palindrome Partitioning

Split a string into every possible list of substrings where each piece is a palindrome. The trick is simple: at each position, try every prefix — and only recurse if that prefix passes a two-pointer palindrome check. Everything else is pruned before the recursive call ever happens.

● MediumBacktrackingTwo PointersDFSTypeScript

PROBLEM What we're solving

Given a string s, return all ways to partition it so that every substring in the partition is a palindrome. Example: s = "aab" → [["a","a","b"],["aa","b"]]. Both partitions cover the whole string and every piece reads the same forwards and backwards. The input s = "a" has exactly one partition: [["a"]].

KEY IDEA Prune at the prefix, not after the recursion

Insight → model the problem as choosing a cut point after position end. For each candidate prefix s[start..end], run a two-pointer check in O(end − start) time. If it is not a palindrome, skip — do not recurse. This prunes the entire subtree before any recursive cost is paid. Only palindrome prefixes open a new branch.

RECIPE Backtrack over cut points, skip non-palindromes

0 · Base case. When start === s.length, the entire string is consumed — push a copy of path into result.
1 · Try every end index. Loop end from start to s.length - 1. Each iteration considers the prefix s[start..end] as the next piece.
2 · Palindrome check. Run two pointers l = start, r = end moving inward. If any pair mismatches, continue to the next end. This prunes the branch without recursing.
3 · Recurse and undo. Push s.slice(start, end + 1) onto path, recurse with backtrack(end + 1, path), then path.pop() to restore state.

Classic confusion → forgetting the path.pop()after the recursive call. Without it, the path accumulates stale entries and every subsequent partition is wrong. The invariant is: push before recurse, pop after recurse — always.

COST Complexity

Generate all 2^n splits, then check each

O(n · 2^n)

Every cut is binary; palindrome check is O(n).

Prune at prefix (this approach)

O(n · 2^n)

Same worst case, but far fewer nodes visited in practice.

Both approaches share an O(n · 2ⁿ) worst-case bound — the number of palindrome partitions can itself be exponential (e.g. "aaa…a"). The improvement from early pruning is practical rather than asymptotic. A DP precomputation of all isPalin[l][r] values reduces each check to O(1) at the cost of O(n²) preprocessing and space — useful when the string is long.

Pattern transfer →the same "try every prefix, recurse on valid ones" skeleton drives Word Break II (valid word instead of palindrome), Restore IP Addresses (valid octet instead of palindrome), and Generate Parentheses (valid open/close count instead of palindrome check).

RUN IT Only recurse on a palindrome prefix

s =

step 0 / 13

STARTStart backtracking on "aab". We try every cut point; only recurse when the prefix is a palindrome.

1▶function partition(s: string): string[][] {
2▶  const result: string[][] = [];
3 
4  function isPalin(l: number, r: number): boolean {
5    while (l < r) {
6      if (s[l] !== s[r]) return false;
7      l++;
8      r--;
9    }
10    return true;
11  }
12 
13▶  function backtrack(start: number, path: string[]): void {
14    if (start === s.length) {
15      result.push([...path]);
16      return;
17    }
18    for (let end = start; end < s.length; end++) {
19      if (!isPalin(start, end)) continue;      // prune non-palindrome prefixes
20      path.push(s.slice(start, end + 1));
21      backtrack(end + 1, path);
22      path.pop();
23    }
24  }
25 
26▶  backtrack(0, []);
27  return result;
28}

current partition(empty)

State

start

end

slice

isPalin

depth

[]

partitions

palindrome prefix — recursenot a palindrome — skipcomplete partition foundbacktracking to parent

slowfast

TYPESCRIPT The solution, annotated

palindromePartitioning.ts
function partition(s: string): string[][] {
  const result: string[][] = [];

  function isPalin(l: number, r: number): boolean {
    while (l < r) {
      if (s[l] !== s[r]) return false;
      l++;
      r--;
    }
    return true;
  }

  function backtrack(start: number, path: string[]): void {
    if (start === s.length) {
      result.push([...path]);
      return;
    }
    for (let end = start; end < s.length; end++) {
      if (!isPalin(start, end)) continue;      // prune non-palindrome prefixes
      path.push(s.slice(start, end + 1));
      backtrack(end + 1, path);
      path.pop();
    }
  }

  backtrack(0, []);
  return result;
}

Reading it block by block

Lines 3–10 — helper isPalin. Two inward-moving pointers starting at l and r. If any pair differs it returns false immediately; otherwise true. O(r − l) per call — no extra space.

Lines 12–24 — backtrack(start, path). The main recursive worker. start is the next unconsumed index; path holds the palindromes chosen so far.

Lines 13–15 — base case. When start === s.length the entire string is covered. We push a copy of path (not the mutable reference) into result.

Lines 16–23 — loop + prune + recurse. For every end from start onward: if isPalin(start, end) is false, continue — the branch dies without a recursive call. Otherwise push the slice, recurse from end + 1, and pop to restore path.

Complexity → Time: O(n · 2ⁿ) in the worst case (an all-same-char string has 2^(n-1) partitions and each palindrome check is O(n)). Space: O(n) recursion depth plus O(n · 2ⁿ) for the output. Precomputing a boolean dp[l][r] table in O(n²) reduces each palindrome check to O(1) without changing the output size.

INTERVIEWFollow-ups they'll ask

"Can you precompute palindrome checks?" Yes — build a 2D boolean table pal[l][r] with DP in O(n²) time and space. Each isPalin call then becomes O(1), which helps when s is long.
"What if you only need the minimum number of cuts?" That is LC 132 — a 1D DP problem. No backtracking needed; precompute palindromes, then cuts[i] = min(cuts[j] + 1) for every palindrome s[j+1..i].
"How would you avoid duplicates if s had repeating characters?" In this problem all partitions are distinct because cut positions encode uniqueness. If the input were a multiset of characters you'd sort and skip duplicate siblings, like in Permutations II.
"What is the recursion depth?" At most n frames (worst case: every single character is its own palindrome). Stack overflow is not a concern for typical constraints (n ≤ 16).
"Trace s="aba" by hand." Prefixes from index 0: "a" (palindrome → recurse), from index 1: "b" (palindrome → recurse), from index 2: "a" (palindrome → base case) → partition ["a","b","a"]; then back to index 1: "ba" (not palindrome, skip); then from index 0: "ab" (not palindrome), then "aba" (palindrome) → base case → ["aba"]. Two total partitions.

MNEMONIC The one-liner

"For each cut point, check the prefix — if it reads the same forwards and back, take it; otherwise skip the whole branch."

TRIGGERS When you see _ → reach for _

"all partitions where each piece is a palindrome"	backtracking over cut points
generating all valid decompositions of a string	try prefix, validate, recurse on suffix
palindrome substring check in a loop	two-pointer l/r check, O(n) per call
"minimum cuts" variant of same problem	1D DP — LC 132, not backtracking

SKELETON The reusable shape

skeleton.ts
function partition(s: string): string[][] {
  const result: string[][] = [];
  function isPalin(l: number, r: number): boolean {
    while (l < r) { if (s[l] !== s[r]) return false; l++; r--; }
    return true;
  }
  function backtrack(start: number, path: string[]): void {
    if (start === s.length) { result.push([...path]); return; }
    for (let end = start; end < s.length; end++) {
      if (!isPalin(start, end)) continue;
      path.push(s.slice(start, end + 1));
      backtrack(end + 1, path);
      path.pop();
    }
  }
  backtrack(0, []);
  return result;
}

FLASHCARDS Tap to flip

What does the base case check in palindrome partitioning?

start === s.length — the entire string is consumed, so path is a complete valid partition. Push a copy into result.

tap to flip

1 / 7

Answer to reveal explanations. No penalty for retries.Score: 0 / 9

QUESTION 01

What is the output of partition("aab")?

QUESTION 02

When a prefix s[start..end] is NOT a palindrome, the algorithm should:

QUESTION 03

What is the time complexity of the backtracking approach with inline two-pointer checks?

QUESTION 04

After backtrack(end + 1, path) returns, what must happen next?

QUESTION 05

How can you improve palindrome checking from O(n) per call to O(1)?

QUESTION 06

How many palindrome partitions does s = "aaa" have?

QUESTION 07

Which sibling problem uses the same "try every valid prefix, recurse on the rest" skeleton?

QUESTION 08

#131 · Palindrome PartitioningBacktracking over prefix lengths: only recurse when the current prefix is a palindrome (checked with two pointers). Record the full partition when the start index reaches the end of the string.Which algorithmic approach does this primarily use?

QUESTION 09

PROBLEM What we're solving

KEY IDEA Prune at the prefix, not after the recursion

RECIPE Backtrack over cut points, skip non-palindromes

COST Complexity

RUN IT Only recurse on a palindrome prefix

TYPESCRIPT The solution, annotated

Reading it block by block

INTERVIEWFollow-ups they'll ask

MNEMONIC The one-liner

TRIGGERS When you see ___ → reach for ___

SKELETON The reusable shape

FLASHCARDS Tap to flip

TRIGGERS When you see _ → reach for _