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
#include <bits/stdc++.h> NEW_LINE using namespace std ; void longestPalindrome ( string s ) { int n = s . length ( ) ; vector < vector < int > > pref ( 26 , vector < int > ( n , 0 ) ) ; vector < vector < int > > pos ( 26 ) ; pref [ s [ 0 ] - ' a ' ] [ 0 ] ++ ; pos [ s [ 0 ] - ' a ' ] . push_back ( 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 ] . push_back ( i ) ; } int ans = 0 ; for ( int i = 0 ; i < 26 ; i ++ ) { int size = pos [ i ] . size ( ) ; ans = 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 = max ( ans , 2 * ( j + 1 ) + sum ) ; } } } cout << ans << " STRNEWLINE " ; } int main ( ) { string S = " bbccdcbb " ; longestPalindrome ( S ) ; return 0 ; }