I recently appeared for Online Assesment of MakeMyTrip (GO-MMT) for SDE-1 (Backend). The test consisted of 20 mcq questions from CS Fundamentals and 2 coding questions to be completed in 90 mins.

This is the first question that was asked.
The second question can be found - HERE

Problem Description : Longest Special Subsequences
You are given a string S of the length n consisting of only lowercase alphabets. If the two consecutive characters in a subsequence have a difference that is no more than k, then it is called a Special Subsequence. Find the length of the longest special subsequence.

INPUT FORMAT :

1. Two space separated integers n and k
2. String S

OUTPUT FORMAT :
Print the length of the longest special subsequence in a new line.

CONSTRAINTS :
1<= n <= (10^5)
1<=k<=26

Sample Input :
7 2
afcbedf

Sample Output :
4

Explaination :
One of the longest special subsequence present in afcbedf is a,c,b,d. It is special because |a-c|<=2 , |c-b|<=2 and |b-d|<=2.

Kindly upvote , if you found this helpful.