Palindrome Partitioning

Cut a string into pieces so every piece reads the same forwards and backwards. For "aab" there are two ways: three single letters, or "aa" followed by "b".

This one's worth doing right after N-Queens because the decision being made is a different shape. There's no board and nothing to place. The choice at each step is where to cut next, and that turns out to fit the same template without any strain.

What a decision is here

Stand at some position in the string with everything before it already cut up. The only question is how long the next piece should be: one character, two, all the way to the end.

So the state is a position, the choices are the possible end points for the next piece, and a choice is allowed when the piece it produces is a palindrome. A complete answer is reaching the end of the string.

That's the entire problem stated in the template's vocabulary, and it took one paragraph, though getting fluent at that translation is most of what this section is actually teaching.

Here it is on "aab," the smallest string with more than one answer.

How the prune differs from N-Queens

Both problems prune, and the two prunes aren't the same kind of thing. The difference is worth noticing, since it decides whether an optimization is even available.

A queen placement gets rejected by comparing it against the other queens already on the board, so the test depends on the whole path you took to get there. Move one queen higher up and the same square might become legal.

A cut gets rejected by looking at the substring alone. Whether "aba" is a palindrome doesn't depend on anything else in the string, or on which cuts came before it. The test depends only on its own inputs.

That independence is exactly what makes precomputation possible. A test that depends only on its inputs can be computed once for every possible input and looked up after that. A test that depends on the path can't.

Precomputing every answer in advance

Checking a palindrome by walking inward from both ends costs time proportional to its length, and the search asks the same questions over and over as it explores different cut positions.

Instead, build a table once, where the entry for i and j says whether the substring from i to j is a palindrome.

isPal[i][j] = true when s[i..j] reads the same both ways

For "aab":
        j=0    j=1    j=2
 i=0    "a"    "aa"   "aab"
        true   true   false
 i=1           "a"    "ab"
               true   false
 i=2                  "b"
                      true

Built once in O(n squared). Every cut test afterwards is a lookup.

The table fills itself using a small observation: a substring is a palindrome when its first and last characters match and the part between them is already known to be one. So work from short substrings outward, or equivalently fill the rows from the bottom up, and every entry you need is already sitting there by the time you reach it.

Building it costs O(n squared) once. After that, every prune in the search is a single array lookup instead of a scan, which matters because the search runs far more of those tests than the table has entries.

Try it

Watch which cuts get rejected. Each rejection removes every partition that would've started with that piece, which on a longer string is a substantial chunk of the tree.

What it costs

The worst case is a string like "aaaa", where every substring is a palindrome and nothing ever gets pruned. Then every gap between characters is independently a cut or not, giving 2 to the power of (n - 1) partitions, and each one costs O(n) to copy out.

That's unavoidable, since the output really is that large. On ordinary strings the prune removes most of the tree, and the gap between the worst case and the typical case is again where the practical value sits.

The implementation

function partition(s) {
  const n = s.length;

  // isPal[i][j]: does s[i..j] read the same both ways?
  const isPal = Array.from({ length: n }, () => new Array(n).fill(false));
  for (let i = n - 1; i >= 0; i--) {
    for (let j = i; j < n; j++) {
      // Ends match, and the inside is already known to be a palindrome.
      isPal[i][j] = s[i] === s[j] && (j - i < 2 || isPal[i + 1][j - 1]);
    }
  }

  const answers = [];
  const current = [];

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

    for (let end = start; end < n; end++) {
      if (!isPal[start][end]) continue;      // the prune, now a lookup

      current.push(s.slice(start, end + 1));
      solve(end + 1);
      current.pop();
    }
  }

  solve(0);
  return answers;
}

Where it goes wrong

Filling the palindrome table in the wrong direction. The entry for i, j needs i + 1, j - 1, a shorter substring starting later. Loop i downward and j upward and everything you need is already there. Get it backwards and you read entries that are still false.

Forgetting the short-substring case. Substrings of length 1 and 2 have nothing inside to check, which is what j - i < 2 handles. Without it the recurrence reads out of bounds or returns false for "aa".

Off-by-one in the slice. The piece runs from start to end inclusive, so the slice needs end + 1 and the recursive call needs end + 1 too. Use end in one but not the other and you get overlapping or gapped pieces.

Recomputing palindromes inside the loop. Correct, and slower by a factor of n. If the table's built anyway, use it.

Check yourself