Palindrome Partitioning

Partition a string so every substring is a palindrome — backtrack with expand checks, list all partitions.

intermediate3 min readUpdated Aug 4, 2026

dsa
backtracking
interview
Google
Meta
Amazon
Microsoft

The problem

Given string s, partition it so every substring in the partition is a palindrome. Return all possible partitions.

Input:  s = "aab"
Output: [["a","a","b"],["aa","b"]]

Input:  s = "a"
Output: [["a"]]

Brute force

All 2^{n-1} ways to cut between characters; filter partitions where every piece is palindrome. Same exponential; backtracking with early palindrome checks is the standard write-up.

Optimal: backtracking

From index start, try every end i such that s[start..i] is palindrome; recurse on i+1.

function partition(s: string): string[][] {
  const res: 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 dfs(start: number): void {
    if (start === s.length) {
      res.push([...path]);
      return;
    }
    for (let end = start; end < s.length; end++) {
      if (!isPal(start, end)) continue;
      path.push(s.slice(start, end + 1));
      dfs(end + 1);
      path.pop();
    }
  }

  dfs(0);
  return res;
}

DP speedup for isPal

Precompute dp[i][j] = whether s[i..j] is palindrome in O(n²), then backtracking only looks up.

function partitionDp(s: string): string[][] {
  const n = s.length;
  const pal = Array.from({ length: n }, () => Array(n).fill(false));
  for (let i = n - 1; i >= 0; i--) {
    for (let j = i; j < n; j++) {
      pal[i][j] = s[i] === s[j] && (j - i <= 1 || pal[i + 1][j - 1]);
    }
  }

  const res: string[][] = [];
  const path: string[] = [];

  function dfs(start: number): void {
    if (start === n) {
      res.push([...path]);
      return;
    }
    for (let end = start; end < n; end++) {
      if (!pal[start][end]) continue;
      path.push(s.slice(start, end + 1));
      dfs(end + 1);
      path.pop();
    }
  }

  dfs(0);
  return res;
}


Time	O(n · 2ⁿ) partitions exploration; + O(n²) if DP table
Space	O(n) recursion + output size

Edge cases

Single char
All same letters — many partitions
No multi-char palindromes — only single-char partition
Empty string → [[]] if allowed

Common bugs

Off-by-one in slice (end exclusive vs inclusive)
Forgetting to copy path when pushing to res
Checking palindrome incorrectly on single characters

Interview delivery

Cut positions + palindrome predicate.
Backtrack from index.
Optional DP precompute.
Complexity exponential in n.
Related: palindrome partitioning min cuts (DP hard variant).

Why backtracking fits

Each cut decision is independent given the prefix partition; you explore all cut sets. Palindrome check prunes invalid cuts early.

DP table fill order

For pal[i][j], need pal[i+1][j-1] already known → iterate i from n-1 down to 0, j from i to n-1.

Palindrome Partitioning II: minimum cuts — pure DP, not listing. Different interview signal (optimization vs enumeration).