Palindrome Partitioning

1. Define the problem

Given a string s, partition s so that every substring of the partition is a palindrome . Return all possible palindrome partitionings of s. Use backtracking that grows the next piece one character at a time from the current start: the instant a candidate piece is a palindrome, add it to the path and recurse on what's left, then undo it to try a longer piece instead.

Constraints

1 ≤ s.length ≤ 16
s consists of only lowercase English letters

Example

Inputs = "aab"

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

Explanation "a" + "a" + "b" and "aa" + "b" are the only two ways to split "aab" into all-palindrome pieces.

2. Know the words first

In plain terms

Palindrome: A string that reads exactly the same forwards and backwards, like 'aa' or 'aba'.

3. Visualize the solution

The row is the list of pieces: grow the next one, keep it only if it's a palindrome

piece 1a

piece 2—

piece 3—

Statustry

The row is the list of pieces cut so far. "a" (index 0) is a palindrome, so it takes the first slot: path=["a"].

What happens in this step

path = ["a"]
piece tried: s[0..0] = "a" — palindrome, try continuing

s = "aab", so the path can hold at most three pieces. backtrack(0) grows the piece starting at index 0 one character at a time; s[0..0]="a" is a palindrome immediately, so it's pushed onto path and backtrack(1) is called on the rest ("ab").

Step 1 of 5

Steps to visualize

The row has one slot per piece the string could be cut into — s = "aab" gives three — and blanks for pieces not cut yet.
Starting from the current position, try extending the next piece one character at a time.
The moment a piece from the start to here is a palindrome, add it to the path and recurse on the rest of the string.
When the whole string has been partitioned, record the path.
Undo the last piece to try a longer one starting from the same position.

4. Walk through the code

Walk through the code

Same walkthrough, now with the code. Press Next to move one step and watch which lines run.

The row is the list of pieces: grow the next one, keep it only if it's a palindrome

piece 1a

piece 2—

piece 3—

Statustry

The row is the list of pieces cut so far. "a" (index 0) is a palindrome, so it takes the first slot: path=["a"].

What happens in this step

path = ["a"]
piece tried: s[0..0] = "a" — palindrome, try continuing

s = "aab", so the path can hold at most three pieces. backtrack(0) grows the piece starting at index 0 one character at a time; s[0..0]="a" is a palindrome immediately, so it's pushed onto path and backtrack(1) is called on the rest ("ab").

Step 1 of 5

5. Solution

Solution

solution.tsTypeScript

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

  function isPalindrome(str, left, right) {
    while (left < right) {
      if (str[left] !== str[right]) return false;
      left++;
      right--;
    }
    return true;
  }

  function backtrack(start) {
    if (start === s.length) {
      result.push(path.slice());
      return;
    }

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

  backtrack(0);
  return result;
}

Time: O(n · 2^n)
Space: O(n)

6. Test cases

Test cases

Input	Expected	Covers
`s = "aab"`	`[["a","a","b"],["aa","b"]]`	example from the docstring
`s = "a"`	`[["a"]]`	smallest valid input, a single character
`s = "aa"`	`[["a","a"],["aa"]]`	both partitionings of a two-character palindrome
`s = "ab"`	`[["a","b"]]`	no multi-character palindromic substring exists
`s = "aba"`	`[["a","b","a"],["aba"]]`	a three-character palindrome with two valid partitionings
`s = "abc"`	`[["a","b","c"]]`	only the all-single-character partitioning is valid
`s = "abb"`	`[["a","b","b"],["a","bb"]]`	the palindromic pair sits at the end of the string

Palindrome Partitioning