Palindrome Partitioning

The problem. Given a string s, split it into pieces so that every piece is a palindrome. Return all the possible splits.

Example

s = "aab"  ->  [["a", "a", "b"], ["aa", "b"]]
s = "a"    ->  [["a"]]
s = "aba"  ->  [["a", "b", "a"], ["aba"]]

The idea: choose where the next piece ends

Each call has a start position — everything before it is already split. The choices are where the next piece ends: any end from start to the last index. A choice is allowed only if s[start..end] is a palindrome; then recurse from end + 1. When start reaches the end of the string, the pieces so far are a complete answer. The palindrome check is the pruning — a non-palindrome piece cuts off its whole subtree.

1. Backtracking with a palindrome check

1function partition(s) {2  const result = [];3  const path = [];4  const isPal = (i, j) => {5    while (i < j) if (s[i++] !== s[j--]) return false;6    return true;7  };8  const cut = (start) => {9    if (start === s.length) {                // the whole string is split10      result.push([...path]);11      return;12    }13    for (let end = start; end < s.length; end++) {14      if (!isPal(start, end)) continue;      // prune: this piece isn't a palindrome15      path.push(s.slice(start, end + 1));    // choose the piece s[start..end]16      cut(end + 1);                          // split the rest17      path.pop();18    }19  };20  cut(0);21  return result;22}

Time O(n · 2ⁿ): a string of n equal letters has 2ⁿ⁻¹ splits, and each palindrome check is O(n). Space O(n) for the path and the call stack.

2. Precompute which pieces are palindromes

The same s[i..j] is checked again and again from different branches. Fill a table first: pal[i][j] is true when s[i] == s[j] and the inside, pal[i+1][j−1], is a palindrome (or there is no inside). Then every check during the search is O(1).

1function partition(s) {2  const n = s.length;3  const pal = Array.from({ length: n }, () => new Array(n).fill(false));4  for (let i = n - 1; i >= 0; i--) {5    for (let j = i; j < n; j++) {6      pal[i][j] = s[i] === s[j] && (j - i < 2 || pal[i + 1][j - 1]);   // ends match, inside is a palindrome7    }8  }9  const result = [];10  const path = [];11  const cut = (start) => {12    if (start === n) {13      result.push([...path]);14      return;15    }16    for (let end = start; end < n; end++) {17      if (!pal[start][end]) continue;        // O(1) check now18      path.push(s.slice(start, end + 1));19      cut(end + 1);20      path.pop();21    }22  };23  cut(0);24  return result;25}

Time O(n · 2ⁿ) still (the output can be that big), but each check is O(1) after an O(n²) table. Space O(n²) for the table. Backtracking plus a DP table is a common pairing in hard problems.

Comparing the approaches

Edge cases to test

Variations