Length of longest Palindromic Subsequence of even length with no two adjacent characters same | C # implementation of the 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
using System ; using System . Collections ; using System . Collections . Generic ; class GFG { static Dictionary < string , int > dp = new Dictionary < string , int > ( ) ; static int solve ( char [ ] 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 . ContainsKey ( new string ( s ) + " ▁ " + c ) ) return dp [ new string ( s ) + " ▁ " + c ] ; int ans = 0 ; if ( s [ 0 ] == s [ s . Length - 1 ] && s [ 0 ] == c ) { for ( char c1 = ' a ' ; c1 <= ' z ' ; c1 ++ ) if ( c1 != c ) { int len = s . Length - 2 ; char [ ] tmp = new char [ len ] ; Array . Copy ( s , 1 , tmp , 0 , len ) ; ans = Math . Max ( ans , 1 + solve ( tmp , c1 ) ) ; } } else { for ( int i = 0 ; i < s . Length ; i ++ ) { if ( s [ i ] == c ) { for ( int j = s . Length - 1 ; j > i ; j -- ) if ( s [ j ] == c ) { if ( j == i ) break ; int len = j + 1 - i ; char [ ] tmp = new char [ len ] ; Array . Copy ( s , i , tmp , 0 , len ) ; ans = solve ( tmp , c ) ; break ; } break ; } } } dp [ new string ( s ) + " ▁ " + c ] = ans ; return dp [ new string ( s ) + " ▁ " + c ] ; } public static void Main ( string [ ] args ) { string s = " abscrcdba " ; int ma = 0 ; for ( char c1 = ' a ' ; c1 <= ' z ' ; c1 ++ ) ma = Math . Max ( ma , solve ( s . ToCharArray ( ) , c1 ) * 2 ) ; Console . Write ( ma + " STRNEWLINE " ) ; } }