Longest subsequence having difference atmost K | C ++ program for the above approach ; Function to find the longest Special Sequence ; Creating a list with all 0 's of size  equal to the length of string ; Supporting list with all 0 's of size 26 since  the given string consists  of only lower case alphabets ; Converting the ascii value to list indices ; Determining the lower bound ; Determining the upper bound ; Filling the dp array with values ; Filling the max_length array with max length of subsequence till now ; return the max length of subsequence ; Driver Code
#include <bits/stdc++.h> NEW_LINE using namespace std ; int longest_subseq ( int n , int k , string s ) { vector < int > dp ( n , 0 ) ; int max_length [ 26 ] = { 0 } ; for ( int i = 0 ; i < n ; i ++ ) { int curr = s [ i ] - ' a ' ; int lower = max ( 0 , curr - k ) ; int upper = min ( 25 , curr + k ) ; for ( int j = lower ; j < upper + 1 ; j ++ ) { dp [ i ] = max ( dp [ i ] , max_length [ j ] + 1 ) ; } max_length [ curr ] = max ( dp [ i ] , max_length [ curr ] ) ; } int ans = 0 ; for ( int i : dp ) ans = max ( i , ans ) ; return ans ; } int main ( ) { string s = " geeksforgeeks " ; int n = s . size ( ) ; int k = 3 ; cout << ( longest_subseq ( n , k , s ) ) ; return 0 ; }