Minimum size substring to be removed to make a given string palindromic | Function to find palindromic prefix of maximum length ; Finding palindromic prefix of maximum length ; Checking if curr substring is palindrome or not . ; Condition to check if the prefix is a palindrome ; if no palindrome exist ; Function to find the maximum size palindrome such that after removing minimum size substring ; Finding prefix and suffix of same length ; Matching the ranges ; Case 1 : Length is even and whole string is palindrome ; Case 2 : Length is odd and whole string is palindrome ; Adding that mid character ; Add prefix or suffix of the remaining string or suffix , whichever is longer ; Reverse the remaining string to find the palindromic suffix ; Driver Code
def palindromePrefix ( S ) : NEW_LINE INDENT n = len ( S ) NEW_LINE for i in range ( n - 1 , - 1 , - 1 ) : NEW_LINE INDENT curr = S [ 0 : i + 1 ] NEW_LINE l = 0 NEW_LINE r = len ( curr ) - 1 NEW_LINE is_palindrome = 1 NEW_LINE while ( l < r ) : NEW_LINE INDENT if ( curr [ l ] != curr [ r ] ) : NEW_LINE INDENT is_palindrome = 0 NEW_LINE break NEW_LINE DEDENT l += 1 NEW_LINE r -= 1 NEW_LINE DEDENT if ( is_palindrome ) : NEW_LINE INDENT return curr NEW_LINE DEDENT DEDENT return " " NEW_LINE DEDENT def maxPalindrome ( S ) : NEW_LINE INDENT n = len ( S ) NEW_LINE if ( n <= 1 ) : NEW_LINE INDENT return S NEW_LINE DEDENT pre = " " NEW_LINE suff = " " NEW_LINE i = 0 NEW_LINE j = n - 1 NEW_LINE while ( S [ i ] == S [ j ] and i < j ) : NEW_LINE INDENT i += 1 NEW_LINE j -= 1 NEW_LINE DEDENT i -= 1 NEW_LINE j += 1 NEW_LINE pre = S [ 0 : i + 1 ] NEW_LINE suff = S [ j : ] NEW_LINE if ( j - i == 1 ) : NEW_LINE INDENT return pre + suff NEW_LINE DEDENT if ( j - i == 2 ) : NEW_LINE INDENT mid_char = S [ i + 1 : i + 2 ] NEW_LINE return pre + mid_char + suff NEW_LINE DEDENT rem_str = S [ i + 1 : j ] NEW_LINE pre_of_rem_str = palindromePrefix ( rem_str ) NEW_LINE list1 = list ( rem_str ) NEW_LINE list1 . reverse ( ) NEW_LINE rem_str = ' ' . join ( list1 ) NEW_LINE suff_of_rem_str = palindromePrefix ( rem_str ) NEW_LINE if ( len ( pre_of_rem_str ) >= len ( suff_of_rem_str ) ) : NEW_LINE INDENT return ( pre + pre_of_rem_str + suff ) NEW_LINE DEDENT else : NEW_LINE INDENT return ( pre + suff_of_rem_str + suff ) NEW_LINE DEDENT DEDENT if __name__ == " _ _ main _ _ " : NEW_LINE INDENT S = " geeksforskeeg " NEW_LINE print ( maxPalindrome ( S ) ) NEW_LINE DEDENT