Given a string input_str consisting of lowercase English letters, determine the minimum number of cuts required to partition input_str such that every substring in the partition is a palindrome. Return the minimum number of cuts needed.
Example 1
Input: input_str = racecarx
Output: 1
Explanation: Partition: [racecar, x] (1 cut)
Example 2
Input: input_str = abcba
Output: 0
Explanation: Partition: [abcba] (no cuts needed, already a palindrome)
Example 3
Input: input_str = civiciv
Output: 1
Explanation: Partition: [civic, iv] (1 cut)
Constraints
Case 1
Input: input_str = 'noonmadam'
Expected: 1
Case 2
Input: input_str = 'xyzzyx'
Expected: 0
Case 3
Input: input_str = 'deifiedlevel'
Expected: 1
Case 4
Input: input_str = 'rotatorpop'
Expected: 1
Case 5
Input: input_str = 'abcdedcba'
Expected: 0