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 <= 2000s consists of lowercase English letters only.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.
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.
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.
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.
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 | 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. |
| 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 |
Palindrome Partitioning II | Using Blue Print | DP On Strings | Leetcode 132 | DP Concepts & Qns-28 • codestorywithMIK • 9,999 views views
Watch 9 more video solutions →Practice Palindrome Partitioning II with our built-in code editor and test cases.
Practice on FleetCode