palindrome_partitioning.py

"""
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: O(n^2)
Space Complexity: O(n^2)
For other explanations refer to: https://www.youtube.com/watch?v=_H8V5hJUGd0
"""


deffind_minimum_partitions(string: str) ->int:
"""
 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
 """
length=len(string)
cut= [0] *length
is_palindromic= [[Falseforiinrange(length)] forjinrange(length)]
fori, cinenumerate(string):
mincut=i
forjinrange(i+1):
ifc==string[j] and (i-j<2oris_palindromic[j+1][i-1]):
is_palindromic[j][i] =True
mincut=min(mincut, 0ifj==0else (cut[j-1] +1))
cut[i] =mincut
returncut[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}")