Palindrome Partitioning (LeetCode 131)

The problem

Given a string s, cut it into one or more pieces so that every piece is a palindrome. Return every possible way to do this. Each answer is a list of the pieces in order.

Input:  s = "aab"
Output: [["a", "a", "b"], ["aa", "b"]]

"a" | "a" | "b" works (single letters are always palindromes), and so does "aa" | "b". "aab" as one piece fails, and so does "a" | "ab".

How to think about it

Start with brute force. A string of length n has n − 1 gaps, and each gap is either cut or not. That’s 2ⁿ⁻¹ partitions. You could generate all of them and keep those whose pieces are all palindromes. Correct, but many partitions fail on their very first piece and you build them anyway.

The key insight: decide the first piece, then the rest is the same problem. Any valid partition starts with some prefix s[0:end] that is a palindrome. Fix that prefix, and what’s left is “partition s[end:]”, which is the same problem on a shorter string. So the recursion is: from position start, try every end; if s[start:end] is a palindrome, take it and recurse from end.

Pruning comes for free. If a prefix isn’t a palindrome, you never recurse on it, so a whole family of partitions is skipped at once. In "aab", the prefix "aab" and the piece "ab" are rejected straight away.

Which pattern is this? Backtracking where each choice is a cut position. The tell is “return all ways to split / partition a string so that each part satisfies X”. Reaching start == len(s) means the whole string was covered, so the path is a complete answer.

Approach

1. bt(start, path): if start == len(s), record a copy of path.
2. Otherwise, for each end from start + 1 to len(s): if s[start:end] is a palindrome, append it, recurse with bt(end, path), pop.
3. Start with bt(0, []).

Solution

def partition_palindrome(s):
    res = []
    def is_pal(t): return t == t[::-1]
    def bt(start, path):
        if start == len(s): res.append(path[:]); return    # whole string covered
        for end in range(start + 1, len(s) + 1):
            if is_pal(s[start:end]):                         # prune: only palindromic pieces
                path.append(s[start:end]); bt(end, path); path.pop()
    bt(0, []); return res
# partition_palindrome("aab") -> [["a","a","b"],["aa","b"]]

Dry run

On s = "aab":

Complexity

• Time: O(n·2ⁿ) worst case. For a string like "aaaa", every one of the 2ⁿ⁻¹ partitions is valid, and each palindrome check and copy costs O(n).
• Space: O(n) for the recursion depth and path, not counting the output.

Edge cases and pitfalls

• Single character returns [["a"]]. An empty string would return [[]], though LeetCode guarantees length ≥ 1.
• All the same letter is the worst case: every partition is valid.
• Off-by-one in the loop. end must go up to len(s) inclusive so the last piece can reach the end: range(start + 1, len(s) + 1).
• Repeated palindrome checks. The same substring can be checked many times. You can precompute an n×n table pal[i][j] with DP to make each check O(1). Mention it as an optimisation.

Related problems

• Palindromic Substrings (LeetCode 647): count the palindromic pieces, using expand-around-centre.
• Word Break (LeetCode 139): the same “choose a prefix, solve the rest” shape, but with DP and a dictionary.
• Subsets (LeetCode 78): the 2ⁿ decision tree this is built on, one choice per gap.