Minimum cuts required to convert a palindromic string to a different palindromic string | Recursive function to find minimum number of cuts if length of string is even ; If length is odd then return 2 ; To check if half of palindromic string is itself a palindrome ; If not then return 1 ; Else call function with half palindromic string ; Function to find minimum number of cuts If length of string is odd ; If length is <= 3 then it is impossible ; Array to store frequency of characters ; Store count of characters in a array ; Condition for edge cases ; If length is even ; If length is odd ; Driver Code
def solveEven ( s ) : NEW_LINE INDENT if len ( s ) % 2 == 1 : NEW_LINE INDENT return 2 NEW_LINE DEDENT ls = s [ 0 : len ( s ) // 2 ] NEW_LINE rs = s [ len ( s ) // 2 : len ( s ) ] NEW_LINE if ls != rs : NEW_LINE INDENT return 1 NEW_LINE DEDENT return solveEven ( ls ) NEW_LINE DEDENT def solveOdd ( s ) : NEW_LINE INDENT return 2 NEW_LINE DEDENT def solve ( s ) : NEW_LINE INDENT if len ( s ) <= 3 : NEW_LINE INDENT return - 1 NEW_LINE DEDENT cnt = [ 0 ] * 25 NEW_LINE for i in range ( 0 , len ( s ) ) : NEW_LINE INDENT cnt [ ord ( s [ i ] ) - ord ( ' a ' ) ] += 1 NEW_LINE DEDENT if max ( cnt ) >= len ( s ) - 1 : NEW_LINE INDENT return - 1 NEW_LINE DEDENT if len ( s ) % 2 == 0 : NEW_LINE INDENT return solveEven ( s ) NEW_LINE DEDENT if len ( s ) % 2 == 1 : NEW_LINE INDENT return solveOdd ( s ) NEW_LINE DEDENT DEDENT if __name__ == " _ _ main _ _ " : NEW_LINE INDENT s = " nolon " NEW_LINE print ( solve ( s ) ) NEW_LINE DEDENT