Minimum cuts required to convert a palindromic string to a different palindromic string | Function to check if string is palindrome or not ; Function to check if it is possible to get result by making just one cut ; Appending last element in front ; Removing last element ; Checking whether string s2 is palindrome and different from s . ; 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 ; Return 1 if it is possible to get palindromic string in just one cut . Else we can always reached in two cuttings . ; Driver Code
def isPalindrome ( s ) : NEW_LINE INDENT for i in range ( len ( s ) ) : NEW_LINE INDENT if ( s [ i ] != s [ len ( s ) - i - 1 ] ) : NEW_LINE INDENT return False NEW_LINE DEDENT DEDENT return true NEW_LINE DEDENT def ans ( s ) : NEW_LINE INDENT s2 = s NEW_LINE for i in range ( len ( s ) ) : NEW_LINE INDENT s2 = s2 [ len ( s2 ) - 1 ] + s2 NEW_LINE s2 = s2 [ 0 : len ( s2 ) - 1 ] NEW_LINE if ( s != s2 and isPalindrome ( s2 ) ) : NEW_LINE INDENT return True NEW_LINE DEDENT DEDENT return False NEW_LINE DEDENT def solve ( s ) : NEW_LINE INDENT if ( len ( s ) <= 3 ) : NEW_LINE INDENT return - 1 NEW_LINE DEDENT cnt = [ 0 for i in range ( 26 ) ] NEW_LINE for i in range ( len ( s ) ) : NEW_LINE INDENT cnt [ ord ( s [ i ] ) - ord ( ' a ' ) ] += 1 NEW_LINE DEDENT max = cnt [ 0 ] NEW_LINE for i in range ( len ( cnt ) ) : NEW_LINE INDENT if cnt [ i ] > max : NEW_LINE INDENT max = cnt [ i ] NEW_LINE DEDENT DEDENT if ( max >= len ( s ) - 1 ) : NEW_LINE INDENT return - 1 NEW_LINE DEDENT else : NEW_LINE INDENT if ans ( s ) == True : NEW_LINE INDENT return 1 NEW_LINE DEDENT else : NEW_LINE INDENT return 2 NEW_LINE DEDENT DEDENT DEDENT if __name__ == ' _ _ main _ _ ' : NEW_LINE INDENT s = " nolon " NEW_LINE print ( solve ( s ) ) NEW_LINE DEDENT