Palindrome Partitioning II
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.
Palindromes overlap and nest. The substring "aba" is a palindrome, but so is "a" and "b" individually. Keeping "aba" as one piece saves cuts compared to splitting it into three single characters. The problem is to find the global optimum when these choices interact.
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 take the one that gives the fewest total cuts.
Key Constraints:
1 <= s.length <= 2000. With n up to 2000, O(n^2) is acceptable (around 4 million operations). An O(n^3) solution that re-checks palindromes inside the DP loop reaches 8 billion operations and times out.sconsists of lowercase English letters only. There is no unicode or case-folding to handle, so character comparison is a direct equality check.
Approach 1: Brute Force (Backtracking)
Intuition
Try every possible way to partition the string and count the cuts. At each position, cut after every valid palindrome prefix, then recursively solve the remainder. Track the minimum total cuts across all valid partitions.
This is a backtracking search over all palindrome partitions. For each starting position, 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:
The recursion starts at solve(0) and tries every palindrome prefix of "aab".
solve(0): prefix candidates are "a" (palindrome) and "aa" (palindrome). "aab" is not a palindrome.- Take "a", then
solve(1): prefix "a" is a palindrome, so take it and callsolve(2). Prefix "b" is a palindrome, take it and callsolve(3), which returns -1 (end reached). Sosolve(2) = 1 + (-1) = 0, andsolve(1) = 1 + 0 = 1. This branch gives1 + solve(1) = 2cuts. - Take "aa", then
solve(2): returns 0 as computed above. This branch gives1 + 0 = 1cut. solve(0)returns the minimum of the two branches:min(2, 1) = 1.
The partition ["aa", "b"] wins with 1 cut.
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 partition, re-checking palindromes and re-solving the same subproblems. The next approach removes both redundancies by precomputing all palindromic substrings and applying dynamic programming over prefixes.
Approach 2: DP with Precomputed Palindrome Table
Intuition
The brute force has two sources of redundancy: repeated palindrome checks and repeated subproblem computation. Dynamic programming eliminates both.
First, precompute a 2D boolean table isPalin[i][j] that records whether s[i..j] is a palindrome. The recurrence: s[i..j] is a palindrome if s[i] == s[j] and s[i+1..j-1] is also a palindrome. The condition j - i <= 2 short-circuits the inner check, since substrings of length 1 or 2 have no interior to verify once the endpoints match.
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 cutting problem reduces to a shortest-path problem on prefixes. Each palindromic substring s[j..i] is an edge from prefix end j-1 to prefix end i with cost 1 cut. The minimum number of cuts for the whole string is the shortest path from the start to position n-1 along these edges.
The recurrence cuts[i] = min(cuts[j-1] + 1) over all palindromic endings s[j..i] considers every possible last partition. Because i increases from left to right, every cuts[j-1] it reads is already final, so each subproblem is solved 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:
- If
isPalin[0][i]is true, setcuts[i] = 0(the whole prefix is a palindrome). - Otherwise, for each j from 1 to i, if
isPalin[j][i]is true, updatecuts[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 palindrome table costs O(n^2) space. The next approach discovers palindromes and updates the cuts array in the same pass, dropping the space to O(n).
Approach 3: Expand Around Center (Optimal)
Intuition
Instead of precomputing all palindrome substrings in a table, the expand-around-center technique finds palindromes during the scan. For each center position, expand outward as long as the characters match. Each palindrome s[left..right] found triggers an update to the cuts array.
A palindrome covering s[left..right] lets us update cuts[right] = min(cuts[right], cuts[left-1] + 1): cut after position left-1, then add s[left..right] as one more palindromic piece. If left is 0, the whole prefix s[0..right] is itself a palindrome and cuts[right] = 0.
Iterating over all centers visits every palindrome once and updates the cuts array as palindromes are discovered, so the 2D table is never built.
Two facts make this safe. First, expanding around every center (n odd centers and n-1 even centers) finds every palindromic substring, because each palindrome has a unique center. So every edge s[left..right] that the DP could use is eventually offered as an update.
Second, the read of cuts[left-1] is always a final value when the update happens. An update to cuts[left-1] requires a palindrome ending at left-1, whose center is at most left-1, which is strictly less than the current center. All such centers were processed in earlier iterations of the outer loop, so cuts[left-1] is settled before any larger center reads it.
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:
- 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.
- 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.