Palindrome Partitioning

The problem

You are given a string s. A partition cuts s into pieces: every letter belongs to exactly one piece, and the pieces keep their order. Return every partition in which each piece is a palindrome, a string that reads the same forwards and backwards. Give each partition as a list of its pieces from left to right. The partitions may come in any order. A single letter is a palindrome, so there is always at least one partition to return.

What to write

function solve(s: string): string[][]

Input
s = "aab"

Output
[["a","a","b"],["aa","b"]]

Input
s = "a"

Output
[["a"]]

Constraints

1 ≤ s.length ≤ 16.

Hints

Each hint gives away a little more. Open one only when you need it.

1. Hint 1: Use the constraints

   The string has at most 16 letters, so there are at most 15 places where a cut could go. That is few enough to try a great many ways of cutting. Every letter must end up in exactly one piece, and a single letter is always a palindrome.

2. Hint 2: Ask a smaller question

   Take aab. Which pieces could come first, starting at the first letter? There are three candidates: a, aa and aab. Which of them are palindromes? For each one that is, which letters are still left to split?

3. Hint 3: Name the pattern

   You must list every partition, and each one is a series of choices: where does the next piece end? That signals backtracking: choose a first piece that is a palindrome, split the rest of the string the same way, then undo the choice and try a longer piece. Read the lesson on backtracking.

4. Hint 4: State the invariant

   At every call, the chosen pieces are all palindromes, and joined together they are exactly the letters of s before the current position. So when the position reaches the end of s, the pieces form a complete partition into palindromes.

5. Hint 5: Sketch the pseudocode

   split(i): if i is the length of s, save a copy of the chosen pieces and return. For each end j from i to the last position: take the piece from i through j. If it reads the same backwards, add it, call split(j + 1), then remove it. Start with split(0).

Solution

From here on the page gives the method away. If you are still solving, go back to the hints.

Approach

At each offset, try every palindromic prefix and recursively partition the remaining suffix.

The slow way

Cut the string in every possible way. Each of the n - 1 gaps between letters is either cut or not, so there are 2^(n-1) ways, 32,768 for 16 letters. Then check every piece of every way. It is correct, but it builds complete partitions whose first piece is already not a palindrome.

The insight

A partition is built from the left, piece by piece. A piece that is not a palindrome can never be repaired by the pieces after it, so test each piece the moment you cut it and go on only after a good one. What is left after a good piece is the same problem on a shorter string.

Step by step

1. Keep the partitions found and the pieces chosen so far. One list collects the finished partitions. The other holds the pieces of the partition being built, and it grows and shrinks as the search goes forward and comes back.
2. No letters are left: save a copy of the chosen pieces. The pieces were cut one after another with no gap, so when no letters are left they cover the whole string. A copy is saved because the working list keeps changing afterwards.
3. Take each piece that starts at the first letter not yet used. The next piece has to begin right after the previous one, so that no letter is skipped or used twice. Its end is the open choice: one letter, two letters, and so on up to the end of the string.
4. Go on only if the piece reads the same backwards. A piece that is not a palindrome can never be part of an answer, whatever follows it. The loop still moves on to longer pieces, because a longer one may be a palindrome again.
5. Choose the piece, split the letters after it, then take it back. With this piece fixed, the letters after it are a smaller copy of the same problem. Taking the piece back afterwards frees its letters, so the loop can try a longer piece from the same place.
6. Start at the first letter with no pieces chosen. Nothing is cut yet, so the first piece must begin at the first letter. When this first call returns, every way of cutting has been tried or ruled out, and the list of partitions is returned.

The same numbered steps are the comments in each solution.

function solve(s) {
  // 1. Keep the partitions found and the pieces chosen so far
  const out = [],
    path = [];
  function visit(i) {
    // 2. No letters are left: save a copy of the chosen pieces
    if (i === s.length) {
      out.push([...path]);
      return;
    }
    // 3. Take each piece that starts at the first letter not yet used
    for (let j = i; j < s.length; j++) {
      const part = s.slice(i, j + 1);
      // 4. Go on only if the piece reads the same backwards
      if (part === [...part].reverse().join("")) {
        // 5. Choose the piece, split the letters after it, then take it back
        path.push(part);
        visit(j + 1);
        path.pop();
      }
    }
  }
  // 6. Start at the first letter with no pieces chosen
  visit(0);
  return out;
}

function solve(s: string): string[][] {
  // 1. Keep the partitions found and the pieces chosen so far
  const out: string[][] = [],
    path: string[] = [];
  function visit(i: number): void {
    // 2. No letters are left: save a copy of the chosen pieces
    if (i === s.length) {
      out.push([...path]);
      return;
    }
    // 3. Take each piece that starts at the first letter not yet used
    for (let j = i; j < s.length; j++) {
      const part = s.slice(i, j + 1);
      // 4. Go on only if the piece reads the same backwards
      if (part === [...part].reverse().join("")) {
        // 5. Choose the piece, split the letters after it, then take it back
        path.push(part);
        visit(j + 1);
        path.pop();
      }
    }
  }
  // 6. Start at the first letter with no pieces chosen
  visit(0);
  return out;
}

def solve(s):
    # 1. Keep the partitions found and the pieces chosen so far
    result = []
    path = []

    def backtrack(i):
        # 2. No letters are left: save a copy of the chosen pieces
        if i == len(s):
            result.append(path.copy())
            return
        # 3. Take each piece that starts at the first letter not yet used
        for j in range(i, len(s)):
            part = s[i : j + 1]
            # 4. Go on only if the piece reads the same backwards
            if part == part[::-1]:
                # 5. Choose the piece, split the letters after it, then take it back
                path.append(part)
                backtrack(j + 1)
                path.pop()

    # 6. Start at the first letter with no pieces chosen
    backtrack(0)
    return result

Example 1, traced

Input
s = "aab"

Output
[["a","a","b"],["aa","b"]]

Why it works

Every partition into palindromes has a first piece, and the loop tries every possible first piece. After a first piece that is a palindrome, the rest of the string is split by the same method, so every answer is found. It is found once, because two different paths differ in where some piece ends. A piece that is not a palindrome is never added.

Time and space

Time O(n² · 2^n) upper bound, extra space O(n + output). Each gap between the n letters is cut or not, giving at most 2^n calls. A call tries up to n pieces of up to n letters, so O(n² · 2^n) is an upper bound: 16 different letters need only 17 calls. Besides the output, pieces and calls take O(n).

n and m are input sizes, h is a tree's height, V and E are a graph's vertices and edges. The bounds describe this reference solution.

Watch out

• Do not stop the loop at the first piece that is not a palindrome. A longer piece can be one again: in aba, the piece ab fails but aba passes. Stopping at ab loses the answer [aba].
• Test the whole piece, not only its two ends. The string abca starts and ends with a, yet it is not a palindrome, and a test of the ends alone would return [abca] as a partition.
• Split on from the letter after the piece, not from its last letter. Otherwise a one-letter piece leads back to the same place and is chosen again and again until the run fails: the calls nest too deep.

Pattern

Backtracking. Builds on Valid Palindrome and Combination Sum.

Keep going