Longest palindromic string possible after removal of a substring | Java Implementation of the above approach ; Function to find the longest palindrome from the start of the String using KMP match ; Append S ( reverse of C ) to C ; Use KMP algorithm ; Function to return longest palindromic String possible from the given String after removal of any subString ; Initialize three Strings A , B AND F ; Loop to find longest subStrings from both ends which are reverse of each other ; Proceed to third step of our approach ; Remove the subStrings A and B ; Find the longest palindromic subString from beginning of C ; Find the longest palindromic subString from end of C ; Store the maximum of D and E in F ; Find the final answer ; Driver Code
import java . util . * ; class GFG { static String findPalindrome ( String C ) { String S = C ; S = reverse ( S ) ; C = C + " & " + S ; int n = C . length ( ) ; int [ ] longestPalindrome = new int [ n ] ; longestPalindrome [ 0 ] = 0 ; int len = 0 ; int i = 1 ; while ( i < n ) { if ( C . charAt ( i ) == C . charAt ( len ) ) { len ++ ; longestPalindrome [ i ] = len ; i ++ ; } else { if ( len != 0 ) { len = longestPalindrome [ len - 1 ] ; } else { longestPalindrome [ i ] = 0 ; i ++ ; } } } String ans = C . substring ( 0 , longestPalindrome [ n - 1 ] ) ; return ans ; } static String findAns ( String s ) { String A = " " ; String B = " " ; String F = " " ; int i = 0 ; int j = s . length ( ) - 1 ; int len = s . length ( ) ; while ( i < j && s . charAt ( i ) == s . charAt ( j ) ) { i = i + 1 ; j = j - 1 ; } if ( i > 0 ) { A = s . substring ( 0 , i ) ; B = s . substring ( len - i , len ) ; } if ( len > 2 * i ) { String C = s . substring ( i , ( s . length ( ) - 2 * i ) + i ) ; String D = findPalindrome ( C ) ; C = reverse ( C ) ; String E = findPalindrome ( C ) ; if ( D . length ( ) > E . length ( ) ) { F = D ; } else { F = E ; } } String answer = A + F + B ; return answer ; } 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 str = " abcdefghiedcba " ; System . out . print ( findAns ( str ) + "NEW_LINE"); } }