Good strings

3.7

11 votes
Dynamic Programming, 2D dynamic programming, Algorithms
Problem

Given a string $$S$$ of length $$N$$ consisting of only lower case alphabets. Print the total count of good strings. A string is called good if:-

- its length is $$N$$ and consists of only lower case alphabets.
- it mismatches with $$S$$ at exactly $$K$$ different indexes.
- it is lexicographically smaller than $$S$$.

Since the answer could be large print it with modulo \(10^9 + 7\).

 Input format

  • The first line contains \(T\) denoting the number of test cases.
  • The first line of each test case contains integers \(N\) and $$K$$, denoting the size of the length of the $$S$$ and mismatch count.
  • The next line contains $$S$$.

Output format

Print the number of total possible good strings. Since the answer could be large print it with modulo \(10^9 + 7\).

Constraints

\(1 \leq T \leq 5000\)
\(1 \leq N \leq 10^5\)
\(1 \leq K \leq 20\)

The sum of \(N\) over all test cases does not exceed \(2 \cdot 10^5\)

Time Limit: 2
Memory Limit: 256
Source Limit:
Explanation

All good strings are $$ abcc,abcb,abca,abbd,abad,aabd $$.

Editor Image

?