Palindrome partitioning II
HardCut where the prefix is a palindrome
Problem
Return the minimum cuts needed to partition a string into palindromes.
Find the fewest cuts so every piece is a palindrome, using a palindrome table plus a cut DP.
The idea
The minimum cuts for a prefix is one more than the best over every split whose second part is a palindrome. Precomputing an isPalindrome table makes each check O(1), giving O(n²) overall.
The trick
- Precompute the palindrome table first, or the check dominates.
- A palindromic whole prefix needs zero cuts — the base case.
- Answer is cuts, so subtract one from the number of parts.
This one walks through the worked example rather than tracing the algorithm frame by frame — a full walkthrough is still to be drawn. The code and the idea below are the real solution.
Step 1 of 2. Here's the example — aab Values: 0.
1dp[i]=min cuts for s[0..i]2if s[j..i] palindrome: dp[i]=min(dp[i], dp[j-1]+1)Input
- array
- [0]
Output
- answer
- —
Check yourself
3 quick questions about this walkthrough. A wrong answer costs nothing.
Examples
Example 1
- Input:
- s = "aab"
- Output:
- 1
- Explanation:
- Cut once: "aa"|"b" → 1 cut.
Example 2
- Input:
- s = "a"
- Output:
- 0
- Explanation:
- Already a palindrome → 0.
Example 3
- Input:
- s = "abccba"
- Output:
- 0
- Explanation:
- The whole thing is a palindrome → 0.
Practice this problem:LeetCode(opens in a new tab)Search GeeksforGeeks(opens in a new tab)
Finished the walkthrough? Add it to your streak.