Palindrome Partitioning

Examples

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

Splitting into "a","a","b" works because each piece reads the same both ways. Splitting into "aa","b" also works. Splitting into "a","ab" does not, because "ab" isn't a palindrome.

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

A single letter is always a palindrome by itself, and there's only one piece possible.

Constraints

• 1 <= s.length <= 16

• s consists only of lowercase English letters.

Approach

Build a partition one piece at a time. At the current starting point in the string, try every possible length for the next piece; if the substring of that length starting here is a palindrome, commit to it as the next piece and recurse on everything after it. When you reach the end of the string, every piece chosen along the way was a palindrome, so the whole path is a valid partition.

A straightforward version of this re-checks "is this substring a palindrome" from scratch every single time it's needed, by comparing characters from both ends inward. That works, but the same substring often gets checked more than once across different partitions being explored.

A faster version precomputes the answer to "is s[i..j] a palindrome" for every possible i and j up front, using the fact that s[i..j] is a palindrome exactly when s[i] equals s[j] and everything strictly between them (s[i+1..j-1]) is also a palindrome. Once that table exists, checking any substring during the search is an instant lookup instead of a fresh scan.

Solutions

Backtracking — Check Each Cut Directly

Starting from a given position, try every possible end point for the next piece. For each candidate piece, scan it from both ends inward to check it's a palindrome; if it is, add it to the current partition, recurse starting right after it, and then remove it before trying a longer (or shorter) next piece.

function partition(s) {
  const result = [];
  const current = [];

  function isPalindrome(start, end) {
    while (start < end) {
      if (s[start] !== s[end]) return false;
      start++;
      end--;
    }
    return true;
  }

  function backtrack(start) {
    if (start === s.length) {
      result.push([...current]);
      return;
    }

    for (let end = start; end < s.length; end++) {
      if (isPalindrome(start, end)) {
        current.push(s.slice(start, end + 1));
        backtrack(end + 1);
        current.pop();
      }
    }
  }

  backtrack(0);
  return result;
}

Time: O(n * 2^n) · Space: O(n) recursion depth, plus output storage

Optimal — Precompute Palindromes with a DP Table

Before searching, build a table isPalindrome[i][j] that says whether s[i..j] is a palindrome, filling it in for shorter substrings first: s[i..j] is a palindrome exactly when s[i] === s[j] and the substring strictly inside them is also a palindrome (or is short enough not to need checking). During the backtracking search, every palindrome check then becomes a single table lookup instead of an O(n) scan.

function partition(s) {
  const n = s.length;
  const isPalindrome = Array.from({ length: n }, () => new Array(n).fill(false));

  for (let end = 0; end < n; end++) {
    for (let start = end; start >= 0; start--) {
      if (s[start] === s[end] && (end - start <= 2 || isPalindrome[start + 1][end - 1])) {
        isPalindrome[start][end] = true;
      }
    }
  }

  const result = [];
  const current = [];

  function backtrack(start) {
    if (start === n) {
      result.push([...current]);
      return;
    }

    for (let end = start; end < n; end++) {
      if (isPalindrome[start][end]) {
        current.push(s.slice(start, end + 1));
        backtrack(end + 1);
        current.pop();
      }
    }
  }

  backtrack(0);
  return result;
}

Time: O(n^2) to precompute the table, plus O(n * 2^n) to generate all partitions - the number of partitions is unavoidable, but each palindrome check during the search is now O(1) instead of O(n) · Space: O(n^2) for the DP table, plus O(n) recursion depth