Longest Palindromic Subsequence of two distinct characters | Java implementation to find Longest Palindromic Subsequence consisting of two distinct characters only ; Function that prints the length of maximum required subsequence ; Calculate length of String ; Store number of occurrences of each character and position of each chatacter in String ; Iterate all characters ; Calculate number of occurences of the current character ; Iterate half of the number of positions of current character ; Determine maximum length of a character between l and r position ; Compute the maximum from all ; Printing maximum length ; Driver Code
import java . util . * ; class GFG { static void longestPalindrome ( String s ) { int n = s . length ( ) ; int [ ] [ ] pref = new int [ 26 ] [ n ] ; Vector < Integer > [ ] pos = new Vector [ 26 ] ; for ( int i = 0 ; i < pos . length ; i ++ ) pos [ i ] = new Vector < Integer > ( ) ; pref [ s . charAt ( 0 ) - ' a ' ] [ 0 ] ++ ; pos [ s . charAt ( 0 ) - ' a ' ] . add ( 0 ) ; for ( int i = 1 ; i < n ; i ++ ) { for ( int j = 0 ; j < 26 ; j ++ ) pref [ j ] [ i ] += pref [ j ] [ i - 1 ] ; int index = s . charAt ( i ) - ' a ' ; pref [ index ] [ i ] ++ ; pos [ index ] . add ( i ) ; } int ans = 0 ; for ( int i = 0 ; i < 26 ; i ++ ) { int size = pos [ i ] . size ( ) ; ans = Math . max ( ans , size ) ; for ( int j = 0 ; j < size / 2 ; j ++ ) { int l = pos [ i ] . elementAt ( j ) ; int r = pos [ i ] . elementAt ( size - j - 1 ) - 1 ; for ( int k = 0 ; k < 26 ; k ++ ) { int sum = pref [ k ] [ r ] - pref [ k ] [ l ] ; ans = Math . max ( ans , 2 * ( j + 1 ) + sum ) ; } } } System . out . print ( ans + "NEW_LINE"); } public static void main ( String [ ] args ) { String S = " bbccdcbb " ; longestPalindrome ( S ) ; } }