Palindrome Partitioning: Fewest Cuts
Advanced
Return the fewest cuts needed to split s into pieces that are all palindromes. A string that is already a palindrome needs 0 cuts.
For "aab" the answer is 1 ("aa" | "b").
The starter code re-checks pieces and repeats work. It is correct but too slow for long strings.
Examples
Example 1
Input:
min_cut_palindromes('aab')
Output:
1
Example 2
Input:
min_cut_palindromes('ab')
Output:
1
Constraints
0 <= len(s) <= 1000- Lower-case letters.
Theory
Go to TheoryKeywords
dsa-sheetdynamic-programmingintervals-and-states
Run your code to see results
No results yet
Run your code to check it against the examples, or submit to run every test.