Given a string input_string consisting of lowercase English letters, determine the minimum number of cuts required to partition input_string such that every substring in the partition is a palindrome. Return the minimum number of cuts needed.
Example 1
Input: input_string = racecarx
Output: 1
Explanation: Partition as [racecar,x] with 1 cut.
Example 2
Input: input_string = noonmadam
Output: 1
Explanation: Partition as [noon,madam] with 1 cut.
Example 3
Input: input_string = abcbaabc
Output: 2
Explanation: Partition as [abcba,a,bc] with 2 cuts.
Constraints
Case 1
Input: input_string = 'levelup'
Expected: 1
Case 2
Input: input_string = 'xyzzyx'
Expected: 0
Case 3
Input: input_string = 'abccbaabccba'
Expected: 1
Case 4
Input: input_string = 'abcdedcba'
Expected: 0
Case 5
Input: input_string = 'aabbcc'
Expected: 2