Watch 10 video solutions for Palindrome Partitioning II, a hard level problem involving String, Dynamic Programming. This walkthrough by NeetCode has 158,858 views views. Want to try solving it yourself? Practice on FleetCode or read the detailed text solution.
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 so every substring is a palindrome. Return the minimum number of cuts required. A single character is already a palindrome, so the goal is minimizing cuts while ensuring each partition reads the same forward and backward.
Approach 1: Dynamic Programming with Palindrome Table (O(n²) time, O(n²) space)
This method precomputes whether every substring s[i..j] is a palindrome using a 2D table. Start with single characters (always palindromes) and expand outward using the relation pal[i][j] = (s[i] == s[j]) && pal[i+1][j-1]. Once palindrome information is known, use a DP array where dp[i] stores the minimum cuts needed for substring s[0..i]. For each index, iterate through possible partition points and update dp[i] = min(dp[i], dp[j-1] + 1) when s[j..i] is a palindrome. The preprocessing eliminates repeated palindrome checks and keeps the solution efficient. This approach heavily uses concepts from dynamic programming and string processing.
Approach 2: Center Expansion with Memoization (O(n²) time, O(n) space)
Instead of storing all palindrome substrings, expand around every possible center. Each index acts as a center for odd-length palindromes, and each pair of indices acts as a center for even-length palindromes. While expanding, update the minimum cut for the right boundary using a DP array. If a palindrome spans from l to r, update dp[r] = min(dp[r], (l == 0 ? 0 : dp[l-1] + 1)). This avoids the full n × n table and calculates palindromes on the fly. The algorithm relies on the classic two pointers center expansion idea and keeps memory usage lower while maintaining the same quadratic time complexity.
Recommended for interviews: The dynamic programming approach with a palindrome table is the most commonly expected solution. It clearly separates palindrome detection and minimum cut calculation, which makes reasoning about correctness easier during an interview. Center expansion shows deeper optimization by reducing memory usage while maintaining O(n²) time, but both demonstrate strong understanding of dynamic programming and palindrome properties.
| Approach | Time | Space | When to Use |
|---|---|---|---|
| Dynamic Programming with Palindrome Table | O(n²) | O(n²) | General case; easiest to reason about and commonly expected in interviews |
| Center Expansion with Memoization | O(n²) | O(n) | When reducing memory usage is important while keeping optimal runtime |