The One Where No One is Ready solution codechef

The One Where No One is Ready solution codechef

Ross has to give an important speech at the museum and he wants all of his friends in the first row of the auditorium. Ross is punctual and gets ready on time.
However, Joey and Chandler are behaving like children and fighting over everything. On getting a firm shouting from Ross, both of them decide to get dressed but they are still angry at each other. Chandler decides to have the final laugh by stealing Joey’s underwear. This makes Joey mad and he decides to wear all the pants owned by Chandler.
This infuriates Ross even more. There is a time crunch and he wants Joey to wear pants of a single color. The One Where No One is Ready solution codechef

Joey has NN pants. Given a string SS of length NN, where SiSi represents the colour of ithith pant. Joey is allowed to make up to KK moves. To make a move, Joey has to do the following:

  • Pick a prefix (possibly empty or complete), say PP from the string SS.
  • Discard a suffix (possibly empty or complete) from PP.
  • Add PP back to the string.

For example, Let the pants be denoted by the string SS = AABADAABAD. In one move Joey can, pick a prefix PP = AABAAABA, discard the suffix ABAABA from PP and finally, add PP = AA back to the string SS. The final string becomes ADAD.

After making up to KK moves, Joey decides to wear the pants denoted by the final string, if all of them are of the same colour.

Find the maximum number of pants that Joey can wear such that all of them are of the same colour, after making at most KK moves. If it is impossible to wear pants of the same colour even after KK moves, print -1.

Input Format The One Where No One is Ready solution codechef

  • First line will contain TT, number of testcases. Then the testcases follow.
  • For each testcase first line of input contains two integers N,KN,K, the number of pants and the maximum number of moves.
  • Second line of each testcase contains a string SS consisting of uppercase english letters. ithith character from the beginning denotes the colour of the ithith layer of pants from top.

Output Format

For each testcase, output in a single line the maximum number of pants of the same colour that Joey can wear using atmost KK moves. If it is impossible for Joey to wear pants of the same colour finally, output -1.

The One Where No One is Ready solution codechef Constraints

  • 1T1001≤T≤100
  • 1N1051≤N≤105
  • 0KN0≤K≤N
  • SS consists of uppercase english letters only.
  • Sum of NN over all test cases does not exceed 21052⋅105

Sample Input 1 

2
5 2
ABACA 
4 1
ABAB

Sample Output 1  The One Where No One is Ready solution codechef

3
1

Explanation

Test case 1: For the first move, Joey can pick the prefix with first 2 pants i.e. ABAB, out of this prefix, Joey can discard the suffix BB and add the remaining prefix i.e. AA back to the string SS. Now the string SS is AACAAACA. For the second move, Joey can pick the prefix with 3 pants i.e. AACAAC, discard the prefix CC and add remaining prefix AAAA back to string. Finally, the string looks like AAAAAA, i.e. 33 pants of colour AA.

Test case 2: For the first and only move, Joey can pick the prefix ABABABAB, i.e. the entire string and discard the suffix BABBAB, and add the remaining prefix i.e. AA back to the string.

Leave a Comment

Your email address will not be published. Required fields are marked *