LeetCode 131 – Palindrome Partitioning

Palindrome Partitioning is backtracking with a filter, and it is the cleanest illustration of a distinction the track has met before: Subsets records at every node, this records only at the leaves. Where the recording happens is decided by the problem, not by taste, and getting it wrong here produces partial partitions in the output.

The problem

Partition a string so that every piece is a palindrome, and return all such partitions.

"aab"  -> [["a","a","b"], ["aa","b"]]

"a"    -> [["a"]]
"aba"  -> [["a","b","a"], ["aba"]]
"abc"  -> [["a","b","c"]]       single characters are always palindromes

Every string has at least one valid partition — cut it into single characters — so the answer is never empty. Noticing that rules out a whole class of "what if none exists" worry.

The shape

At each position, try every prefix starting there. If the prefix is a palindrome, take it and recurse on the rest; otherwise skip it.

"aab" from index 0:
  "a"   palindrome -> recurse at 1
          "a"  -> recurse at 2
                 "b" -> recurse at 3 == length, RECORD ["a","a","b"]
          "ab" not a palindrome, skip
  "aa"  palindrome -> recurse at 2
          "b" -> RECORD ["aa","b"]
  "aab" not a palindrome, skip

The base case is start == s.length(): the string has been consumed exactly, so the path is a complete partition. That is the difference from Subsets — a partial path here is not an answer, it is a partition of a prefix, and recording it would put ["a"] in the output for input "aab".

Java

class Solution {
    public List<List<String>> partition(String s) {
        List<List<String>> out = new ArrayList<>();
        backtrack(s, 0, new ArrayList<>(), out);
        return out;
    }

    private void backtrack(String s, int start, List<String> path, List<List<String>> out) {
        if (start == s.length()) {
            out.add(new ArrayList<>(path));   // COPY -- path keeps mutating
            return;                            // only complete partitions count
        }

        for (int end = start + 1; end <= s.length(); end++) {
            if (isPalindrome(s, start, end - 1)) {
                path.add(s.substring(start, end));
                backtrack(s, end, path, out);
                path.remove(path.size() - 1);  // undo
            }
        }
    }

    /** Is s[lo..hi] a palindrome? Inclusive on both ends. */
    private boolean isPalindrome(String s, int lo, int hi) {
        while (lo < hi) {
            if (s.charAt(lo++) != s.charAt(hi--)) return false;
        }
        return true;
    }
}

The defensive copy is the same one Subsets needs, and for the same reason: storing path directly gives you a list of references to an object that is empty by the time the function returns.

isPalindrome checks in place with two indices rather than building a substring and reversing it. That matters more than it looks: this function is called O(n²) times, and allocating in it is how a slow solution gets slow.

Python

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

        def backtrack(start: int) -> None:
            if start == len(s):
                out.append(path[:])            # a copy, via a slice
                return

            for end in range(start + 1, len(s) + 1):
                piece = s[start:end]
                if piece == piece[::-1]:       # cheap and clear at this size
                    path.append(piece)
                    backtrack(end)
                    path.pop()

        backtrack(0)
        return out

piece == piece[::-1] allocates a reversed copy, which the two-pointer version avoids. At LeetCode's limit of 16 characters that is irrelevant and the clarity wins; on a longer string it would not be. Saying which trade you made is the point.

Precomputing the palindrome table

The same substrings get tested repeatedly across branches. A table computed once removes that entirely:

isPal[i][j] = s[i] == s[j] AND (j - i < 2 OR isPal[i+1][j-1])

Fill it by increasing length so the inner value is ready when it is needed. That is O(n²) once, after which every check in the backtracking is a single array read.

It does not change the asymptotic bound, because the output already dominates — but it is the right answer to "can you avoid the repeated work?", and the recurrence is the same one behind Longest Palindromic Substring. Palindrome Partitioning II (132) asks for the minimum number of cuts, and there the table is not an optimisation but a requirement.

Complexity

A string of length n has n - 1 possible cut positions, each independently taken or not, so there are 2ⁿ⁻¹ partitions in the worst case — "aaaa…a", where every one of them is valid. Building each costs O(n).

That worst case is worth naming: the exponential comes from the answer being exponential, not from the search being wasteful. "Make it faster" is asking to return less.

The pattern

Three backtracking problems, three different recording rules — and lining them up is more useful than any one of them:

The loop, the undo and the copy are identical in all four. Only the base case and the legality test differ.

What the interviewer is checking

• That recording happens only at start == s.length(), not at every node.
• The defensive copy of the path.
• That the palindrome check is in place rather than allocating.
• Single characters counting as palindromes, so an answer always exists.
• That the exponential bound is the output size, not wasted search.
• That you can offer the precomputed table when asked about repeated work.
• Single-character and all-same-character strings.