How to solve problems related to subsequences? Which topics should I Learn to solve it?

Below is a sample question , Like that questions I am always unable to solve it.
Anyone can tell which topics should I cover to solve problems like given below.

In simple words How to solve problems related to subsequences? What should I learn recursion, DP?

PROBLEM STATEMENT:

Ishita is going to her friend Marge's house. There she stumbles upon an old box. She opens the box and finds a paper. On top of the paper a string is written consisting of only lowercase letters.

The string is of length N. She reads further and finds some instructions are written on the bottom of the page.
1) Choose a subsequence from the above string such that the difference between every two neighbouring characters is not more than K.
2) Choose a subsequence which has the longest length.
3) Find that longest length.

Suddenly Marge comes up and sees her reading the paper. She tells her it's an old game she used to play with her grandmother. Ishita is very interested and tries the game. Can you help Ishita find the length of the longest such subsequence?

INPUT FORMAT :
Each line contains two integers N and K and a string S.

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

CONSTRAINTS:
1 <= N <= 10^5
1 <= K <= 26

 
SAMPLE INPUT:
7 2 afcbedg

SAMPLE OUTPUT:
4

EXPLANATION:
One of the longest sequence present in "afcbedf" is a, c, b, d.
It is valid because |a - c| <= 2, |c - b| <= 2 and | b-d| <= 2.
Comments (1)