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.
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.
C++
Java
Python
C#
JavaScript
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.
C++
Java
Python
C#
JavaScript
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²) | 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 |
Palindrome Partitioning - Backtracking - Leetcode 131 • NeetCode • 158,858 views views
Watch 9 more video solutions →Practice Palindrome Partitioning II with our built-in code editor and test cases.
Practice on FleetCodePractice this problem
Open in Editor