Description
Given a string s, return the minimum cuts needed to partition s such that every substring of the partition is a palindrome.
Examples
Input:
s = "aab"Output:
1Explanation:
Cut once: ["aa", "b"].
Input:
s = "a"Output:
0Explanation:
Edge case returning zero.
Input:
s = "raceacar"Output:
2Explanation:
The optimal partition is 'r|aceca|r' with 2 cuts, where 'r', 'aceca', and 'r' are all palindromes. The middle segment 'aceca' is the longest palindromic substring, minimizing the number of cuts needed.
Constraints
- •
1 ≤ s.length ≤ 2000 - •
s consists of lowercase English letters.