Palindrome Partitioning II
Last Updated: March 28, 2026
Understanding the Problem
We need to split a string into pieces where every piece reads the same forwards and backwards. The goal is to minimize the number of cuts. A string of length n can be split into at most n pieces (each character on its own), requiring n-1 cuts. But if we can find longer palindromic substrings, we can cover more characters with fewer pieces.
The challenge is that palindromes can overlap and nest in complex ways. The substring "aba" is a palindrome, but so is "a" and "b" individually. Choosing to keep "aba" as one piece saves cuts compared to splitting it into three single characters. The question is how to find the global optimum when these choices interact.
The key observation: this is an optimization problem with overlapping subproblems. If we know the minimum cuts for every prefix of the string, we can build up the answer incrementally. For each position, we check all palindromes that end at that position and see which one gives us the fewest total cuts.
Key Constraints:
1 <= s.length <= 2000--> With n up to 2000, O(n^2) is the sweet spot. O(n^3) brute force with palindrome checking at each step is borderline and likely TLE.sconsists of lowercase English letters only --> 26 possible characters. No special characters or unicode to worry about.
Approach 1: Brute Force (Backtracking)
Intuition
The most natural approach is to try every possible way to partition the string and count the cuts. At each position, we try cutting after every valid palindrome prefix, then recursively solve the remainder. We track the minimum total cuts across all valid partitions.
This is essentially a backtracking search over all palindrome partitions. For each starting position, we extend the substring character by character, check if it forms a palindrome, and if so, recurse on the rest.
Algorithm
- Start at index 0 of the string.
- For each index i, try every ending index j from i to n-1.
- If s[i..j] is a palindrome, make a cut after j and recursively find the minimum cuts for s[j+1..n-1].
- The answer for starting index i is 1 + min(recursive result) over all valid j. If the entire remaining string is a palindrome, the answer is 0 (no cut needed for this segment).
- Return the result for starting index 0.
Example Walkthrough
Input:
Try all partitions: ["a","a","b"] needs 2 cuts. ["aa","b"] needs 1 cut. "aab" is not a palindrome, so we cannot use 0 cuts.
Output:
Code
- Time Complexity: O(n * 2^n). In the worst case, every substring could be a palindrome, leading to 2^(n-1) possible partitions. At each recursive call, we also spend O(n) checking palindromes.
- Space Complexity: O(n). The recursion depth is at most n.
The brute force explores every possible partition, redundantly re-checking palindromes and re-solving the same subproblems. What if we precomputed all palindromic substrings and used DP to avoid repeated work?
Approach 2: DP with Precomputed Palindrome Table
Intuition
The brute force has two sources of redundancy: repeated palindrome checks and repeated subproblem computation. We can eliminate both with dynamic programming.
First, we precompute a 2D boolean table isPalin[i][j] that tells us whether s[i..j] is a palindrome. The recurrence is elegant: s[i..j] is a palindrome if s[i] == s[j] and s[i+1..j-1] is also a palindrome (or j - i <= 2, meaning the inner portion has 0 or 1 characters).
Then we define cuts[i] as the minimum number of cuts needed for the prefix s[0..i]. For each position i, we check every starting position j from 0 to i. If s[j..i] is a palindrome, then we could place a cut before j and use the result from cuts[j-1]. The answer is cuts[n-1].
The base case: if the entire prefix s[0..i] is a palindrome, then cuts[i] = 0.
The palindrome table captures the structure of the string completely. Once we know every palindromic substring, the cutting problem becomes a shortest-path problem on prefixes. Each palindromic substring s[j..i] represents an "edge" from prefix j-1 to prefix i, with a cost of 1 cut. Finding the minimum cuts for the full string is equivalent to finding the shortest path from the beginning to the end using these edges.
The DP recurrence cuts[i] = min(cuts[j-1] + 1) for all valid palindromic endings ensures we consider every possible last partition. By building from left to right, each subproblem is solved exactly once.
Algorithm
- Build a 2D table
isPalinwhereisPalin[i][j]is true if s[i..j] is a palindrome. Fill it bottom-up: iterate i from n-1 down to 0, and j from i to n-1. - Create an array
cutsof size n. Initializecuts[i] = i(worst case: i cuts for i+1 characters). - For each position i from 0 to n-1:
a. If isPalin[0][i] is true, set cuts[i] = 0 (the whole prefix is a palindrome).
b. Otherwise, for each j from 1 to i, if isPalin[j][i] is true, update cuts[i] = min(cuts[i], cuts[j-1] + 1).
- Return
cuts[n-1].
Example Walkthrough
Code
- Time Complexity: O(n^2). Building the palindrome table takes O(n^2). The cuts DP also takes O(n^2) in the worst case.
- Space Complexity: O(n^2). The palindrome table uses O(n^2) space. The cuts array uses O(n).
The O(n^2) space for the palindrome table works, but we can do better. What if we discovered palindromes and updated the cuts array in a single pass, avoiding the 2D table entirely?
Approach 3: Expand Around Center (Optimal)
Intuition
Instead of precomputing all palindrome substrings in a table, we can use the classic "expand around center" technique to find palindromes on the fly. For each center position in the string, we expand outward as long as the characters match. Each time we find a palindrome s[left..right], we immediately update the cuts DP.
Here is the key insight. A palindrome centered at position center covers s[left..right]. When we find such a palindrome, we can update cuts[right] = min(cuts[right], cuts[left-1] + 1). If left is 0, the entire prefix is a palindrome and cuts[right] = 0.
By iterating over all centers and expanding, we visit each palindrome exactly once. The cuts array gets updated as palindromes are discovered, so we never need the 2D palindrome table.
The expand-around-center technique guarantees we discover every palindromic substring. For each center, expansion stops as soon as characters mismatch. Every palindrome s[left..right] found triggers a potential update to cuts[right], considering the cost of cuts[left-1] + 1.
The correctness relies on the fact that we visit all centers from left to right. When we update cuts[right] using cuts[left-1], the value cuts[left-1] is already finalized because left-1 < center, and all centers that could affect cuts[left-1] have already been processed.
Algorithm
- Create an array
cutsof size n. Initializecuts[i] = ifor all i (worst case: i cuts for i+1 characters). - For each center position c from 0 to n-1:
a. Expand for odd-length palindromes: set left = c, right = c. While left >= 0, right < n, and s[left] == s[right], update cuts[right] and expand.
b. Expand for even-length palindromes: set left = c, right = c+1. Same expansion logic.
- When updating cuts[right]: if left == 0, set cuts[right] = 0. Otherwise, cuts[right] = min(cuts[right], cuts[left-1] + 1).
- Return cuts[n-1].
Example Walkthrough
Code
- Time Complexity: O(n^2). We iterate over n centers. For each center, the expansion can extend at most O(n) positions in each direction.
- Space Complexity: O(n). We only use the cuts array of size n. No 2D table needed.