Longest subsequence with different adjacent characters | C ++ program for the above approach ; dp table ; A recursive function to find the update the dp [ ] [ ] table ; If we reach end of the string ; If subproblem has been computed ; Initialise variable to find the maximum length ; Choose the current character ; Omit the current character ; Return the store answer to the current subproblem ; Function to find the longest Subsequence with different adjacent character ; Length of the string s ; Initialise the memoisation table ; Return the final ans after every recursive call ; Driver Code ; Function call
#include <bits/stdc++.h> NEW_LINE using namespace std ; int dp [ 100005 ] [ 27 ] ; int calculate ( int pos , int prev , string & s ) { if ( pos == s . length ( ) ) { return 0 ; } if ( dp [ pos ] [ prev ] != -1 ) return dp [ pos ] [ prev ] ; int val = 0 ; if ( s [ pos ] - ' a ' + 1 != prev ) { val = max ( val , 1 + calculate ( pos + 1 , s [ pos ] - ' a ' + 1 , s ) ) ; } val = max ( val , calculate ( pos + 1 , prev , s ) ) ; return dp [ pos ] [ prev ] = val ; } int longestSubsequence ( string s ) { int n = s . length ( ) ; memset ( dp , -1 , sizeof ( dp ) ) ; return calculate ( 0 , 0 , s ) ; } int main ( ) { string str = " ababa " ; cout << longestSubsequence ( str ) ; return 0 ; }