Palindrome Partitioning LeetCode 131 Guide

LeetCode 131 Palindrome Partitioning asks: given a string s, partition it such that every substring of the partition is a palindrome, and return all possible palindrome partitions. For example, s = "aab" produces [["a","a","b"], ["aa","b"]]. Unlike problems that ask for a single optimal answer, this one demands every valid partition — making it a classic backtracking enumeration problem.

The key insight is that we must try every possible first cut: take s[0..0], s[0..1], ..., s[0..n-1] as the first part. If the chosen prefix is a palindrome, recurse on the remaining suffix. If not, skip that cut. This gives a decision tree where each level corresponds to choosing the next palindrome segment.

The naïve approach checks palindromes using a two-pointer scan in O(k) time at each node, leading to O(n * 2^n) work overall — since there can be up to 2^(n-1) partitions. The optimized approach precomputes a boolean isPalindrome[i][j] table in O(n²) time using DP, reducing each palindrome check during backtracking to O(1).

The brute-force approach generates all possible partitions by trying every prefix of the current suffix as the next segment. Starting from index 0, try substrings s[0..0], s[0..1], s[0..2], and so on. For each prefix, check if it is a palindrome using a two-pointer scan from both ends inward.

If the prefix is a palindrome, add it to the current path and recurse on the remaining suffix starting at the next index. When the start index reaches the end of the string, the current path is a complete partition — add a copy of it to the result list. After returning from recursion, pop the last segment (backtrack) and continue trying longer prefixes.

While correct, this is slow in practice because the palindrome check is O(k) for a substring of length k, and the same substring may be checked many times across different branches of the recursion tree. For the all-lowercase input constraint (n ≤ 16), this is acceptable, but the optimized DP approach is preferred in interviews to show deeper understanding.

The optimization is to precompute whether every substring s[i..j] is a palindrome before running backtracking. Define isPalindrome[i][j] = true if s[i..j] is a palindrome. The base cases are: every single character isPalindrome[i][i] = true, and every two-character substring isPalindrome[i][i+1] = (s[i] == s[i+1]).

For substrings of length 3 or more, use the recurrence: isPalindrome[i][j] = (s[i] == s[j]) and isPalindrome[i+1][j-1]. This says that s[i..j] is a palindrome if the outer characters match and the inner substring is also a palindrome. Fill the table for increasing lengths: first length 1, then 2, then 3, and so on. This ensures that when computing isPalindrome[i][j], the inner result isPalindrome[i+1][j-1] is already computed.

The table takes O(n²) time and O(n²) space to build. During the backtracking phase, every palindrome check is then a simple O(1) table lookup instead of an O(k) scan. For n = 16 this is a modest improvement, but for larger inputs the constant-time lookup makes a significant practical difference in the number of operations performed.

With the isPalindrome table precomputed, the backtracking function changes only in one place: instead of calling a palindrome-check helper, simply look up isPalindrome[start][end]. If isPalindrome[start][end] is false, skip that prefix immediately without doing any character comparison work.

This lookup-based pruning has the same logical behavior as the brute force — it still explores the same recursive tree structure — but each pruning decision is O(1) instead of O(k). The total time complexity remains O(n * 2^n) in the worst case (when all substrings are palindromes, as in "aaa...a"), but average-case performance improves substantially because invalid branches are cut faster.

The pruning also makes the code cleaner. Rather than embedding a palindrome-check loop inside the backtracking loop, you have a pure lookup, separating concerns: the DP phase is responsible for palindrome knowledge, and the backtracking phase is responsible for enumeration. This separation is a hallmark of good algorithm design.

Take s = "aab". The root of the decision tree starts at index 0 with an empty path. Level 1 choices: try "a" (isPalindrome[0][0] = true → recurse on "ab"), try "aa" (isPalindrome[0][1] = true → recurse on "b"), try "aab" (isPalindrome[0][2] = false → skip). Already we see the DP table saving work: "aab" is immediately ruled out.

From the "a" branch (remaining "ab", start=1): try "a" (isPalindrome[1][1] = true → recurse on "b"), try "ab" (isPalindrome[1][2] = false → skip). From the "a","a" branch (remaining "b", start=2): try "b" (isPalindrome[2][2] = true → base case reached, path = ["a","a","b"] → add to results). From the "aa" branch (remaining "b", start=2): try "b" (isPalindrome[2][2] = true → base case, path = ["aa","b"] → add to results).

The final result is [["a","a","b"], ["aa","b"]]. Notice how the decision tree mirrors the subproblem structure: each node represents a remaining suffix, and each edge represents choosing the next palindrome prefix. The DP table is what makes edge decisions instant, and the backtracking ensures every valid complete path is collected.

In Python: first build the isPalindrome table with a nested loop over lengths and starting indices. Then define backtrack(start, path) as a closure. In the loop from start to len(s), check isPalindrome[start][end-1] (0-indexed). If true, path.append(s[start:end]), call backtrack(end, path), then path.pop(). The base case appends list(path) to results. Call backtrack(0, []) and return results.

In Java: allocate boolean[][] isPalindrome = new boolean[n][n]. Fill single-char diagonals, two-char pairs, then all longer lengths. For backtracking, use a List<List<String>> result and a LinkedList<String> path. In the recursive method, loop end from start to n, check isPalindrome[start][end], and if true add s.substring(start, end+1), recurse, then remove last. The base case adds new ArrayList<>(path) to result.

Both implementations run cleanly for n ≤ 16. The Python version benefits from readable slice syntax (s[start:end]) while Java requires explicit substring calls. In either language, the structure is the same: O(n²) setup followed by standard backtracking with O(1) palindrome lookups.

Palindrome Partitioning is a perfect example of a problem where two paradigms — backtracking and dynamic programming — work together rather than competing. The DP handles the precomputation of a structural property (is this substring a palindrome?), while backtracking handles the enumeration of all valid combinations. This pairing appears frequently in hard interview problems.

Word Break II (LeetCode 140) is the closest structural analog: precompute which prefixes are valid words (using a set lookup or DP), then backtrack to enumerate all valid sentence splits. Subsets II (LeetCode 90) and Combination Sum II (LeetCode 40) follow a similar backtracking-with-pruning pattern where duplicate handling requires careful sorting and skipping. Recognizing the "enumerate all solutions with pruning" shape helps you quickly reach for backtracking.

For the "count partitions" variant (LeetCode 132 Palindrome Partitioning II), pure DP is the right tool — you only need the minimum number of cuts. But for the "return all partitions" problem (LeetCode 131), backtracking is essential because you must explicitly construct every valid answer. Understanding this distinction between counting problems (DP) and enumeration problems (backtracking) is a key algorithmic insight.