Given a string s, partition it into substrings so that every substring is a palindrome and return the minimum number of cuts needed. Pattern focus: Interval DP. Reuse palindrome checks for intervals and compute the best cut position for each prefix.
s = input string
minimum number of cuts needed to partition s into palindromic substrings
Example 1:
Input:
s = "aab"
Output:
1
Explanation:
The partition [aa | b] uses one cut.
Example 2:
Input:
s = "a"
Output:
0
Explanation:
A single character is already a palindrome.
Example 3:
Input:
s = "abccbc"
Output:
2
Explanation:
One optimal partition is [a | bccb | c].