Longest special subsequences

★★★★★

2.7

13 votes

Algorithms, Dynamic Programming, Java, Medium, Optimization, Python, Two dimensional

Details

Submissions

Discussion

Editorial

Problem

You are given a string S of the length n consisting of only lowercase English 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

First line: t (number of test cases)
Next t line: Three space-separated integers n, k, and S

Output format

For each test case, print the length of the longest special subsequence in a new line.

Constraints

$1 \le t \le 10$

$1 \le n \le 10^{5}$

$1 \le k \le 26$

Time Limit: 1

Memory Limit: 256

Source Limit:

Explanation

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