Minimum size substring to be removed to make a given string palindromic | Java program of the above approach ; 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
import java . util . * ; class GFG { static String palindromePrefix ( String S ) { int n = S . length ( ) ; for ( int i = n - 1 ; i >= 0 ; i -- ) { String curr = S . substring ( 0 , i + 1 ) ; int l = 0 , r = curr . length ( ) - 1 ; boolean is_palindrome = true ; while ( l < r ) { if ( curr . charAt ( l ) != curr . charAt ( r ) ) { is_palindrome = false ; break ; } l ++ ; r -- ; } if ( is_palindrome ) return curr ; } return " " ; } static String maxPalindrome ( String S ) { int n = S . length ( ) ; if ( n <= 1 ) { return S ; } String pre = " " , suff = " " ; int i = 0 , j = n - 1 ; while ( S . charAt ( i ) == S . charAt ( j ) && i < j ) { i ++ ; j -- ; } i -- ; j ++ ; pre = S . substring ( 0 , i + 1 ) ; suff = S . substring ( j ) ; if ( j - i == 1 ) { return pre + suff ; } if ( j - i == 2 ) { String mid_char = S . substring ( i + 1 , i + 2 ) ; return pre + mid_char + suff ; } String rem_str = S . substring ( i + 1 , j ) ; String pre_of_rem_str = palindromePrefix ( rem_str ) ; rem_str = reverse ( rem_str ) ; String suff_of_rem_str = palindromePrefix ( rem_str ) ; if ( pre_of_rem_str . length ( ) >= suff_of_rem_str . length ( ) ) { return pre + pre_of_rem_str + suff ; } else { return pre + suff_of_rem_str + suff ; } } static String reverse ( String input ) { char [ ] a = input . toCharArray ( ) ; int l , r = a . length - 1 ; for ( l = 0 ; l < r ; l ++ , r -- ) { char temp = a [ l ] ; a [ l ] = a [ r ] ; a [ r ] = temp ; } return String . valueOf ( a ) ; } public static void main ( String [ ] args ) { String S = " geeksforskeeg " ; System . out . print ( maxPalindrome ( S ) ) ; } }