All Tracks Algorithms Searching Binary Search Problem

Sumit's love for Pokemons
Tag(s):

Easy

Problem
Editorial
Analytics

Sumit is very fond of Pokemons and spend all his pocket money buying pokemon cards only. One day, his friend Himanshu introduced him to a game called 'Pokeball', where participants can win a large number of pokemon cards.

'Pokeball' is a game in which you are given a string consisting of English letters (both upper case and lower case). Each of these letters corresponds to a unique pokemon cards. Now as usual there are some rules in the game.

A participant can change one of the letters in the sequence and make it to represent other type of pokemon cards. This move is called a Kalti move. Each game has some fixed number of Kalti moves allowed. You need to find ‘L’ i.e. the maximum length of consecutive characters of the string where all letters denotes the same pokemon cards using at most ‘k’ Kalti moves. If your answer is right then you will get ‘L’ no. of pokemon cards as reward. Upper case and lower case letters represent different type of Pokemon Cards. Since; Sumit is busy watching ‘Game of Thrones’, Can you solve this problem for him?

Note: 'A' and 'a' represents different Pokemon Cards.

Input: First line contain T, number of test cases.

The first line of the test case contains two integers n and k (1 ≤ n ≤ 100 000, 0 ≤ k ≤ n) — the length of the string and the maximum number of Kalti Moves.

The second line of the test case contains the string, consisting of lower case letters and upper case letters only.

Output: For each test case output one new line containing the required output ‘L’ i.e. the maximum no. of pokemon cards Sumit can win.

Constraint:

  • 1≤ T≤ 12
  • 1 ≤ n ≤ 100 000
  • 0 ≤ k ≤ n
  • String will be made up of lower case and upper case letters only.

Scoring :

  • 40 points (String is made up of letters 'a' and 'b' only).
  • 60 points : Original constraint
SAMPLE INPUT
2
4 1
aaab
6 2
bbaaba
SAMPLE OUTPUT
4
5
Explanation

In first test case, we can get string aaaa by changing last letter b with a .

In the second case, we can change the string to get bbbbba.

Time Limit: 1.0 sec(s) for each input file.
Memory Limit: 256 MB
Source Limit: 1024 KB
Marking Scheme: Marks are awarded when all the testcases pass.
Allowed Languages: Bash, C, C++, C++14, Clojure, C#, D, Erlang, F#, Go, Groovy, Haskell, Java, Java 8, JavaScript(Rhino), JavaScript(Node.js), Julia, Kotlin, Lisp, Lisp (SBCL), Lua, Objective-C, OCaml, Octave, Pascal, Perl, PHP, Python, Python 3, R(RScript), Racket, Ruby, Rust, Scala, Swift, Swift-4.1, TypeScript, Visual Basic

CODE EDITOR

Initializing Code Editor...
Your Rating:

Contributor

This Problem was Asked in

ABV- Indian Institute of Information Technology and Management, Gwalior

Challenge Name

CodeMaze v3.0

OTHER PROBLEMS OF THIS CHALLENGE
Notifications
View All Notifications

?