hardDynamic Programming 1DPure DSA~45 min
Minimum Splits Into Palindromic Chunks
A symmetric-encoding pipeline can only ship palindromic chunks. Given a string, find the fewest cuts needed so every resulting piece reads the same forwards and backwards.
Problem
Given a string s, partition it so every substring is a palindrome, and return the minimum number of cuts needed. A string of length k that is already a palindrome needs 0 cuts.
Input
A string s (1 ≤ |s| ≤ 2000) of lowercase letters.
Output
An integer: the minimum number of cuts.
Constraints
- 1 ≤ |s| ≤ 2000
- Every final piece must be a palindrome
- Cuts are between characters
Examples
Example 1
Input
s = "aab"
Output
1
Cut once into 'aa' | 'b', both palindromes.
Example 2
Input
s = "racecar"
Output
0
The whole string is already a palindrome.