ALG-H019HardDynamic Programming
Fewest Palindrome Splits
Split text into contiguous non-empty palindromic pieces using as few cuts as possible. Return the number of cuts. Empty text needs zero cuts.
Contract
input text: string
return integer
Constraints
- • 0 <= text length <= 2000
Examples
Example 1
text = "aab"
→ 1
Example 2
text = "a"
→ 0
5 judge tests (2 shown above). Target complexity: O(n^2).