Length of longest Palindromic Subsequence of even length with no two adjacent characters same | C ++ implementation of above approach ; To store the values of subproblems ; Function to find the Longest Palindromic subsequence of even length with no two adjacent characters same ; Base cases If the string length is 1 return 0 ; If the string length is 2 ; Check if the characters match ; If the value with given parameters is previously calculated ; If the first and last character of the string matches with the given character ; Remove the first and last character and call the function for all characters ; If it does not match ; Then find the first and last index of given character in the given string ; Take the substring from i to j and call the function with substring and the given character ; Store the answer for future use ; Driver code ; Check for all starting characters
#include <bits/stdc++.h> NEW_LINE using namespace std ; #define lli  long long int NEW_LINE unordered_map < string , lli > dp ; lli solve ( string s , char c ) { if ( s . length ( ) == 1 ) return 0 ; if ( s . length ( ) == 2 ) { if ( s [ 0 ] == s [ 1 ] && s [ 0 ] == c ) return 1 ; else return 0 ; } if ( dp [ s + " ▁ " + c ] ) return dp [ s + " ▁ " + c ] ; lli ans = 0 ; if ( s [ 0 ] == s [ s . length ( ) - 1 ] && s [ 0 ] == c ) { for ( char c1 = ' a ' ; c1 <= ' z ' ; c1 ++ ) if ( c1 != c ) ans = max ( ans , 1 + solve ( s . substr ( 1 , s . length ( ) - 2 ) , c1 ) ) ; } else { for ( lli i = 0 ; i < s . length ( ) ; i ++ ) { if ( s [ i ] == c ) { for ( lli j = s . length ( ) - 1 ; j > i ; j -- ) if ( s [ j ] == c ) { if ( j == i ) break ; ans = solve ( s . substr ( i , j - i + 1 ) , c ) ; break ; } break ; } } } dp [ s + " ▁ " + c ] = ans ; return dp [ s + " ▁ " + c ] ; } int main ( ) { string s = " abscrcdba " ; lli ma = 0 ; for ( char c1 = ' a ' ; c1 <= ' z ' ; c1 ++ ) ma = max ( ma , solve ( s , c1 ) * 2 ) ; cout << ma << endl ; return 0 ; }