Palindrome Partitioning II - Solution & Explanation
Problem Statement
Given a string s, partition s such that every substring of the partition is a palindrome.
Return the minimum cuts needed for a palindrome partitioning of s.
Example 1:
Input: s = "aab" Output: 1 Explanation: The palindrome partitioning ["aa","b"] could be produced using 1 cut.
Example 2:
Input: s = "a" Output: 0
Example 3:
Input: s = "ab" Output: 1
Constraints:
1 <= s.length <= 2000sconsists of lowercase English letters only.
Approach Overview
Problem Overview: Given a string s, split it into substrings such that every substring is a palindrome. Return the minimum number of cuts required. A single character is already a palindrome, but longer segments must read the same forward and backward.
Approach 1: Dynamic Programming with Palindrome Table (Time: O(n^2), Space: O(n^2))
This method precomputes whether every substring s[i..j] is a palindrome. Use a 2D boolean table where pal[i][j] becomes true if the characters match and the inner substring s[i+1..j-1] is also a palindrome. Once this table is built, compute the minimum cuts using a DP array cuts[i] representing the minimum cuts needed for prefix s[0..i]. For each index, iterate backward to find valid palindrome segments and update cuts[i]. The precomputed palindrome table removes repeated checks, giving an overall O(n^2) time solution. This approach is common in dynamic programming problems involving substring partitions.
Approach 2: Center Expansion with Memoization (Time: O(n^2), Space: O(n))
Instead of storing all palindrome substrings, expand around each center to detect palindromes dynamically. For every index, expand for both odd and even length palindromes using two pointers moving outward. When a palindrome s[l..r] is found, update the minimum cuts needed for position r using previously computed results. A memoized DP array tracks the best cut count for every prefix of the string. This avoids the n × n palindrome table while still exploring all valid centers. The technique relies on the symmetry property of palindromes and is a common pattern in string problems involving substring checks.
Recommended for interviews: The dynamic programming approach with a palindrome table is the most expected answer. It clearly separates two ideas: detecting palindromes and minimizing cuts. Interviewers like this solution because the reasoning is easy to explain and guarantees O(n^2) time. The center expansion method is slightly more space efficient and demonstrates deeper understanding of palindrome properties, which can stand out in strong DP interviews.
Approach 1: Dynamic Programming with Palindrome Table
This approach involves using two DP tables. One to check if a substring is a palindrome and another to compute the minimum cuts required.
We maintain a 2D boolean table where palindrome[i][j] is true if the substring s[i...j] is a palindrome. Using this table, we calculate the minimum number of palindrome partitions.
The solution builds a palindrome table by iterating through the string. It checks every substring and stores whether it is a palindrome or not. Then we use this table to compute the minimum cuts for each position in the string. Cuts are initialized assuming each character needs a cut, and the DP table is updated accordingly for each palindrome found.
Complexity
Time Complexity: O(n^2) due to filling the palindrome table and computing cuts.
Space Complexity: O(n^2) as well for the DP tables storage.
Approach 2: Center Expansion with Memoization
This approach utilizes the idea of expanding around potential palindrome centers, combined with a memoization strategy to store minimum cuts. It significantly reduces redundant calculations by only considering centers and keeping track of the best solutions observed so far.
In C, the memoization version checks around potential palindrome centers and expands outwards. It maintains an array for the minimum cuts needed, updating it as palindromes are detected with less cutting as the criteria.
Complexity
Time Complexity: O(n^2) due to potentially expanding and updating cuts for each center.
Space Complexity: O(n) focused on the cuts array.
Approach 3: Dynamic Programming
First, we preprocess the string s to determine whether each substring s[i..j] is a palindrome, and record this in a 2D array g[i][j], where g[i][j] indicates whether the substring s[i..j] is a palindrome.
Next, we define f[i] to represent the minimum number of cuts needed for the substring s[0..i-1]. Initially, f[i] = i.
Next, we consider how to transition the state for f[i]. We can enumerate the previous cut point j. If the substring s[j..i] is a palindrome, then f[i] can be transitioned from f[j]. If j = 0, it means that s[0..i] itself is a palindrome, and no cuts are needed, i.e., f[i] = 0. Therefore, the state transition equation is as follows:
$
f[i] = min_{0 leq j leq i} \begin{cases} f[j-1] + 1, & if\ g[j][i] = True \ 0, & if\ g[0][i] = True \end{cases}
The answer is f[n], where n is the length of the string s.
The time complexity is O(n^2), and the space complexity is O(n^2). Here, n is the length of the string s$.
Complexity Comparison
| Approach | Complexity |
|---|---|
| Dynamic Programming with Palindrome Table | Time Complexity: O(n^2) due to filling the palindrome table and computing cuts. |
| Center Expansion with Memoization | Time Complexity: O(n^2) due to potentially expanding and updating cuts for each center. |
| Dynamic Programming | — |
Detailed Complexity Analysis
| Approach | Time | Space | When to Use |
|---|---|---|---|
| Dynamic Programming with Palindrome Table | O(n^2) | O(n^2) | Standard interview solution when clarity is more important than memory usage |
| Center Expansion with Memoization | O(n^2) | O(n) | When you want to avoid storing the full palindrome table and compute palindromes on the fly |
Video Solution
DP 53. Palindrome Partitioning - II | Front Partition 🔥 • take U forward • 194,138 views views
Watch 9 more video solutions →Frequently Asked Questions
Is Palindrome Partitioning II easy or hard?
How to solve Palindrome Partitioning II in O(n^2)?
Palindrome Partitioning II Python or Java solution?
What is the best approach for Palindrome Partitioning II?
What data structure is used in Palindrome Partitioning II?
What is the time complexity of Palindrome Partitioning II?
Is Palindrome Partitioning II asked at Google, Amazon, or Meta?
Ready to solve this problem?
Practice Palindrome Partitioning II with our built-in code editor and test cases.
Practice on FleetCode