given a string s partition s such that every substring of the partition is a palindrome find the minimum cuts needed for a palindrome partitioning of s time complexity on2 space complexity on2 for other explanations refer to https www youtube comwatch vh8v5hjugd0 returns the minimum cuts needed for a palindrome partitioning of string findminimumpartitionsaab 1 findminimumpartitionsaaa 0 findminimumpartitionsababbbabbababa 3 returns the minimum cuts needed for a palindrome partitioning of string find_minimum_partitions aab 1 find_minimum_partitions aaa 0 find_minimum_partitions ababbbabbababa 3
def find_minimum_partitions(string: str) -> int:
    
    length = len(string)
    cut = [0] * length
    is_palindromic = [[False for i in range(length)] for j in range(length)]
    for i, c in enumerate(string):
        mincut = i
        for j in range(i + 1):
            if c == string[j] and (i - j < 2 or is_palindromic[j + 1][i - 1]):
                is_palindromic[j][i] = True
                mincut = min(mincut, 0 if j == 0 else (cut[j - 1] + 1))
        cut[i] = mincut
    return cut[length - 1]


if __name__ == "__main__":
    s = input("Enter the string: ").strip()
    ans = find_minimum_partitions(s)
    print(f"Minimum number of partitions required for the '{s}' is {ans}")