4.18.7 — Palindrome Partitioning

LeetCode 131 · Medium · ★ Blind 75

The problem

Cut the string into pieces so that every piece is a palindrome. Return all possible ways.

"aab"  →  [["a","a","b"], ["aa","b"]]

The string is at most 16 characters.

The pattern

The choices here are not elements — they are cut positions.

Think of this like having a long chocolate bar made of several connected squares, and a knife. You can place your knife at any of the joints between the squares and make a cut. When you make a cut, you examine the piece you just broke off. If it's a valid palindrome, you put it in your pile and look at the remaining bar, deciding where to cut next. If the piece isn't a palindrome, you magically undo that cut and try cutting further down the bar instead.

Standing at index start, the piece you take next can end anywhere from start to the end of the string. Each ending is one branch. Take the piece only if it is a palindrome, recurse from just after it, then undo.

"aab", starting at 0:

  take "a"    → recurse from 1
      take "a"   → recurse from 2
          take "b" → recurse from 3 = end → record ["a","a","b"] ✓
      take "ab"  → not a palindrome, rejected
  take "aa"   → recurse from 2
      take "b"   → end → record ["aa","b"] ✓
  take "aab"  → not a palindrome, rejected

This is the same start-index loop as 4.18.1 Subsets. Only the meaning of the loop variable changed: it is a cut point rather than an item index.

Recognising that is the point of the problem. When you can phrase the choices as "what do I take next, and where does it end", the template is unchanged.

The solution

Python

class Solution:
    def partition(self, s: str) -> List[List[str]]:
        result = []
        path = []

        def is_palindrome(lo: int, hi: int) -> bool:
            while lo < hi:
                if s[lo] != s[hi]:
                    return False
                lo += 1
                hi -= 1
            return True

        def backtrack(start: int):
            if start == len(s):                     # consumed the whole string
                result.append(path[:])
                return

            for end in range(start, len(s)):        # the piece is s[start..end]
                if not is_palindrome(start, end):
                    continue                        # prune: not a valid piece

                path.append(s[start:end + 1])
                backtrack(end + 1)                  # continue after this piece
                path.pop()

        backtrack(0)
        return result

TypeScript

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

  function isPal(lo: number, hi: number): boolean {
    while (lo < hi) {
      if (s[lo] !== s[hi]) return false;
      lo++; hi--;
    }
    return true;
  }

  function backtrack(start: number): void {
    if (start === s.length) {
      result.push([...path]);
      return;
    }
    for (let end = start; end < s.length; end++) {
      if (!isPal(start, end)) continue;

      path.push(s.slice(start, end + 1));
      backtrack(end + 1);
      path.pop();
    }
  }

  backtrack(0);
  return result;
}

The palindrome check is the pruning, and it happens before recursing. That is what stops the search exploring every one of the 2^{n-1} possible cuttings — most branches die at the check.

is_palindrome takes indices, not a substring. Passing s[start:end+1] would allocate a new string on every check, which is O(n) of pure waste per call. Comparing in place with two pointers is the same discipline as 4.2 and 4.5.1.

backtrack(end + 1) — the next piece starts immediately after the one just taken.

The base case is start == len(s), meaning the whole string has been consumed. There is no leftover to worry about, because every branch takes a piece and moves past it.

Precomputing the palindromes

The palindrome check costs O(n) and is called from every node of the tree, and many of those checks repeat. You can compute all of them once, in O(n^2), with a small dynamic program:

n = len(s)
pal = [[False] * n for _ in range(n)]
for hi in range(n):
    for lo in range(hi, -1, -1):
        if s[lo] == s[hi] and (hi - lo < 2 or pal[lo + 1][hi - 1]):
            pal[lo][hi] = True

Read the condition: s[lo..hi] is a palindrome when its two ends match and the inside is already known to be one. hi - lo < 2 covers the pieces of length 1 and 2, which have no inside.

The loop order matters — lo counts downwards so that pal[lo+1][hi-1] is already filled when it is needed. That "fill the table in an order where the dependencies already exist" idea is the core of 4.24.

With the table, is_palindrome(lo, hi) becomes an O(1) lookup and the whole search drops a factor of n. Say this even if you do not write it — recognising the repeated work is the observation being tested.

Complexity

O(2^{n-1} \times n) in the worst case. A string of n characters has n−1 gaps and each is either cut or not, so there are 2^{n-1} possible partitions; copying each result costs O(n).

The worst case is a string like "aaaa", where every piece is a palindrome and nothing is ever pruned. On ordinary strings the pruning removes almost everything.

O(n) space for the recursion, or O(n^2) with the precomputed table.

Let's break this down:

• Time Complexity: There are n-1 possible cut points in a string of length n. For each cut point, we either make a cut or we don't, giving 2^{n-1} possible partitions. For each valid partition, we slice and copy strings, taking O(n) time. The palindrome check itself takes O(n) string traversal, giving O(n \cdot 2^{n-1}) total worst-case time (like the string "aaaaa"). The DP precomputation reduces the inner check to O(1), but the copying still binds the overall worst case to O(n \cdot 2^{n-1}).
• Space Complexity: The maximum depth of the recursion tree is n (if we cut every single character). The path array stores at most n items. If we use the DP table, it takes O(n^2) space. So O(n) or O(n^2) depending on the approach.

Where this goes next

• Palindrome Partitioning II — the minimum number of cuts. Enumerating every partition and taking the smallest is far too slow. Because you only need an optimum rather than every answer, it becomes DP: O(n^2). 4.23.
• Word Break II — cut a string into dictionary words and return all of them. Identical template with the dictionary check replacing the palindrome check.
• Restore IP Addresses — cut a digit string into four valid octets. Same template, with a validity check and a piece-count limit.

The recurring dividing line: all the answers means backtracking; the best answer or how many means DP. Combination Sum II and Combination Sum IV sit on either side of it, and so do these two Palindrome Partitioning problems.

What the interviewer will push on

"What are the choices at each step?" Where the next piece ends.

"Where is the pruning?" The palindrome check before recursing.

"Why pass indices instead of substrings to the checker?" Slicing allocates and costs O(n) per check.

"Can you avoid re-checking the same substrings?" Precompute an n \times n table in O(n^2).

"What if you only needed the minimum number of cuts?" DP, not backtracking, and say why: you want one optimum, not every arrangement.

One thing to volunteer: point out that this is the subsets template where the loop variable is a cut position. Naming the reused skeleton is worth more than the code.

Next: 4.18.8 Letter Combinations of a Phone Number — the simplest possible branching, driven by a lookup table.