Longest subsequence with different adjacent characters | 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 ; Return the final ans after every recursive call ; Driver Code ; Function call
dp = [ [ - 1 for i in range ( 27 ) ] for j in range ( 100005 ) ] ; NEW_LINE def calculate ( pos , prev , s ) : NEW_LINE INDENT if ( pos == len ( s ) ) : NEW_LINE INDENT return 0 ; NEW_LINE DEDENT if ( dp [ pos ] [ prev ] != - 1 ) : NEW_LINE INDENT return dp [ pos ] [ prev ] ; NEW_LINE DEDENT val = 0 ; NEW_LINE if ( ord ( s [ pos ] ) - ord ( ' a ' ) + 1 != prev ) : NEW_LINE INDENT val = max ( val , 1 + calculate ( pos + 1 , ord ( s [ pos ] ) - ord ( ' a ' ) + 1 , s ) ) ; NEW_LINE DEDENT val = max ( val , calculate ( pos + 1 , prev , s ) ) ; NEW_LINE dp [ pos ] [ prev ] = val ; NEW_LINE return dp [ pos ] [ prev ] ; NEW_LINE DEDENT def longestSubsequence ( s ) : NEW_LINE INDENT n = len ( s ) ; NEW_LINE return calculate ( 0 , 0 , s ) ; NEW_LINE DEDENT if __name__ == ' _ _ main _ _ ' : NEW_LINE INDENT str = " ababa " ; NEW_LINE print ( longestSubsequence ( str ) ) ; NEW_LINE DEDENT