Remove a character from a string to make it a palindrome | Utility method to check if substring from low to high is palindrome or not . ; This method returns - 1 if it is not possible to make string a palindrome . It returns - 2 if string is already a palindrome . Otherwise it returns index of character whose removal can make the whole string palindrome . ; Initialize low and right by both the ends of the string ; loop until low and high cross each other ; If both characters are equal then move both pointer towards end ; If removing str [ low ] makes the whole string palindrome . We basically check if substring str [ low + 1. . high ] is palindrome or not . ; If removing str [ high ] makes the whole string palindrome We basically check if substring str [ low + 1. . high ] is palindrome or not ; We reach here when complete string will be palindrome if complete string is palindrome then return mid character ; Driver Code
def isPalindrome ( string : str , low : int , high : int ) -> bool : NEW_LINE INDENT while low < high : NEW_LINE INDENT if string [ low ] != string [ high ] : NEW_LINE INDENT return False NEW_LINE DEDENT low += 1 NEW_LINE high -= 1 NEW_LINE DEDENT return True NEW_LINE DEDENT def possiblepalinByRemovingOneChar ( string : str ) -> int : NEW_LINE INDENT low = 0 NEW_LINE high = len ( string ) - 1 NEW_LINE while low < high : NEW_LINE INDENT if string [ low ] == string [ high ] : NEW_LINE INDENT low += 1 NEW_LINE high -= 1 NEW_LINE DEDENT else : NEW_LINE INDENT if isPalindrome ( string , low + 1 , high ) : NEW_LINE INDENT return low NEW_LINE DEDENT if isPalindrome ( string , low , high - 1 ) : NEW_LINE INDENT return high NEW_LINE DEDENT return - 1 NEW_LINE DEDENT DEDENT return - 2 NEW_LINE DEDENT if __name__ == " _ _ main _ _ " : NEW_LINE INDENT string = " abecbea " NEW_LINE idx = possiblepalinByRemovingOneChar ( string ) NEW_LINE if idx == - 1 : NEW_LINE INDENT print ( " Not ▁ possible " ) NEW_LINE DEDENT elif idx == - 2 : NEW_LINE INDENT print ( " Possible ▁ without ▁ removing ▁ any ▁ character " ) NEW_LINE DEDENT else : NEW_LINE INDENT print ( " Possible ▁ by ▁ removing ▁ character ▁ at ▁ index " , idx ) NEW_LINE DEDENT DEDENT