Longest Palindromic Subsequence of two distinct characters | C # 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
using System ; using System . Collections . Generic ; class GFG { static void longestPalindrome ( String s ) { int n = s . Length ; int [ , ] pref = new int [ 26 , n ] ; List < int > [ ] pos = new List < int > [ 26 ] ; for ( int i = 0 ; i < pos . Length ; i ++ ) pos [ i ] = new List < int > ( ) ; pref [ s [ 0 ] - ' a ' , 0 ] ++ ; pos [ s [ 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 [ i ] - ' a ' ; pref [ index , i ] ++ ; pos [ index ] . Add ( i ) ; } int ans = 0 ; for ( int i = 0 ; i < 26 ; i ++ ) { int size = pos [ i ] . Count ; ans = Math . Max ( ans , size ) ; for ( int j = 0 ; j < size / 2 ; j ++ ) { int l = pos [ i ] [ j ] ; int r = pos [ i ] [ 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 ) ; } } } Console . Write ( ans + " STRNEWLINE " ) ; } public static void Main ( String [ ] args ) { String S = " bbccdcbb " ; longestPalindrome ( S ) ; } }