LeetCode 131 - Palindrome Partitioning

Palindrome Partitioning asks for every way to cut a string s so that each piece is itself a palindrome. Unlike Two Sum or Group Anagrams, there's no single clever data structure that solves it in one pass — the honest answer is that you have to explore the whole search space, and the interview signal is in how cleanly you do that.

Watch: LeetCode 131 walkthrough

The backtracking shape

At each position, try every prefix starting there. If that prefix is a palindrome, keep it as one piece and recurse on the rest of the string. If it isn't, skip it and try a longer prefix. When you reach the end of the string, the pieces you've collected along the current path are one valid partition.

function backtrack(start, path):
    if start == len(s):
        result.append(path.copy())
        return
    for end in start+1 .. len(s):
        piece = s[start:end]
        if isPalindrome(piece):
            path.append(piece)
            backtrack(end, path)
            path.pop()

This is plain backtracking: choose, recurse, undo. The only interesting decision is what counts as a valid choice at each step, which is exactly the palindrome check.

The naive palindrome check is the bottleneck

Checking whether a substring is a palindrome by walking it from both ends is O(n) per check. Since backtracking already explores an exponential number of partitions, doing an O(n) check at every branch multiplies an already-expensive search by another factor of n for no reason — the string itself doesn't change between calls, so the same substrings get re-checked over and over across different branches.

Precompute palindromes with DP

Build a table isPal[i][j] that answers "is s[i..j] a palindrome" in O(1), filled once up front in O(n^2):

isPal[i][i] = true                          // single char
isPal[i][i+1] = (s[i] == s[i+1])             // two chars
isPal[i][j] = (s[i] == s[j]) and isPal[i+1][j-1]   // general case

Filling this table by increasing substring length (so isPal[i+1][j-1] is already known) turns every palindrome check inside the backtracking loop into a single array lookup. The backtracking still has to enumerate every valid partition — that part is inherently exponential in the worst case (a string of all the same character has an exponential number of valid partitions) — but the table removes the redundant work of re-deriving the same palindrome facts from scratch on every branch.

Complexity

With the table: O(n^2) to build it, and the backtracking itself is bounded by the number of partitions times the work to copy each one, which is the part of the problem that's genuinely exponential — no algorithm avoids it, since the output size itself can be exponential. The DP table is what keeps the per-step cost down to O(1) instead of O(n), which is the difference between a solution that passes and one that times out on longer strings.

The follow-up interviewers ask

Once you have this working, the natural next question is LeetCode 132, Palindrome Partitioning II: instead of returning every partition, return the minimum number of cuts needed. That's a different DP on top of the same isPal table — minCuts[j] is the fewest cuts needed for s[0..j], computed as min(minCuts[i-1] + 1) over every i <= j where s[i..j] is a palindrome. Having the palindrome table already built makes that second DP a short addition rather than a rewrite, which is usually the point of asking it.