Palindromic Partitioning Problem Statement

Given a string ‘str’, calculate the minimum number of partitions required to ensure every resulting substring is a palindrome.

Input:

The first line contains an integer ‘T’, the number of test cases. The following ‘T’ lines, each contains a string ‘str’ for partition analysis.

Output:

Return the minimum number of cuts needed to partition each string into palindromic substrings for every test case.

Example:

Input:

T = 1
str = "AACCB"

Output:

2

Explanation:

The valid partition "A | A | CC | B" makes all substrings palindromes, requiring 2 cuts.

Constraints:

• 1 <= T <= 50
• 1 <= length(string) <= 100
• The string consists of uppercase English alphabets only.
• Time limit: 1 second

Notes:

1) Partitions can be made after the first and before the last index. 
2) Each substring post-partition must be a palindrome.
3) If the string is a palindrome, 0 cuts are needed. 
4) If all characters in the string are unique, 'n-1' cuts are needed, where 'n' is the string length.