All submissions for this problem are available.
Devu is a freshman in the college. In the data structures course, he has recently learned about LCS (longest common subsequence) problem, He thought about this problem a lot and has finally come up with a challenge for you.
You are given a string S of size N consisting only of lowercase English letters ('a' to 'z'). You have to find minimum length of string V also consisting of lowercase English letters('a' to 'z') such that length of LCS (S, V) ≥ L. The string V should not have more than K consecutive equal characters.
Note that it is not necessary for string V to be composed of characters of S only.
- First line contains T : number of test cases.
- For each test case, You are given two lines.
- First line contains a string S.
- Second line contains two space separated integers K and L.
- For each test case, output a single line containing integer corresponding to the answer of the problem.
- 1 ≤ T ≤ 106
- 1 ≤ Size of string S ≤ 106
- 1 ≤ Sum of lengths of strings over all test cases ≤ 107
- 1 ≤ K, L ≤ Size of S
- For first test case, V is 'a'.
- For second test case, V can be 'ab' or 'ba'.
|Time Limit:||2 sec|
|Source Limit:||50000 Bytes|
|Languages:||C, CPP 4.3.2, CPP 4.9.2, GO, JAVA|
Fetching successful submissions