Beautiful String

SUB Inter University Prog...
Limits 10s, 512 MB

You are given a binary string S of length N, and a value K. You need to find a maximum length of a beautiful string which is a sub-string of S. A beautiful string is a binary string where absolute difference of zero’s and one’s occurrence is no more than K.

Input

Input starts with a value T<=100 (Total number of test case).
For every input first line contains 1<=N<=1000000 and 0<=K<=N. And next line contains a binary string of length N.

Output

Output format is Case X: Y where X is the case number test case and Y is the maximum length of the Beautiful String.

Sample

InputOutput
2
7 2
0101000
7 1
0101000
Case 1: 6
Case 2: 5

Submit

Login to submit.

Statistics

100% Solution Ratio
ashraful9194Earliest, 3w ago
ashraful9194Fastest, 0.2s
ashraful9194Lightest, 2.7 MB
ashraful9194Shortest, 1162B
Toph uses cookies. By continuing you agree to our Cookie Policy.