Longest subsequence with different adjacent characters | Java 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
class GFG { static int dp [ ] [ ] = new int [ 100005 ] [ 27 ] ; static 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 . charAt ( pos ) - ' a ' + 1 != prev ) { val = Math . max ( val , 1 + calculate ( pos + 1 , s . charAt ( pos ) - ' a ' + 1 , s ) ) ; } val = Math . max ( val , calculate ( pos + 1 , prev , s ) ) ; return dp [ pos ] [ prev ] = val ; } static int longestSubsequence ( String s ) { int n = s . length ( ) ; for ( int i = 0 ; i < 100005 ; i ++ ) { for ( int j = 0 ; j < 27 ; j ++ ) { dp [ i ] [ j ] = - 1 ; } } return calculate ( 0 , 0 , s ) ; } public static void main ( String [ ] args ) { String str = " ababa " ; System . out . print ( longestSubsequence ( str ) ) ; } }