Binary Search : The Key of Universe

Source of Question

Question

High school student Vasya got a string of length n as a birthday present. This string consists of letters 'a' and 'b' only. Vasya denotes beauty of the string as the maximum length of a substring (consecutive subsequence) consisting of equal letters.

Vasya can change no more than k characters of the original string. What is the maximum beauty of the string he can achieve?

Input

The first line of the input contains two integers n and k (1 ≤ n ≤ 100 000, 0 ≤ k ≤ n) — the length of the string and the maximum number of characters to change.

The second line contains the string, consisting of letters 'a' and 'b' only.

Output

Print the only integer — the maximum beauty of the string Vasya can achieve by changing no more than k characters.

Examples

input

4 2
abba

output

4

input

8 1
aabaabaa

output

5

Note

In the first sample, Vasya can obtain both strings "aaaa" and "bbbb".

In the second sample, the optimal answer is obtained with the string "aaaaabaa" or with the string "aabaaaaa".

Solution

I think you already read the question but in short, you have given a string and a number k 

you have to find the length of the longest substring such that after replacing at most k character( possible none ) all the characters are same of that substring.

Think about how to solve this problem🤔

Way 1 : An intuitive approach ( Two Pointer )

Take two pointers i = 0 and j = 0 and increase i till the condition holds, when the condition fails then increase j  till condition fails. The answer is the max value of i - j + 1 for all i , j when conditions is satisfied. 

Time Complexity : O( 2N ) = O(N) , here N = length of string.

Code:

int main(){
 int n , k , ans = 0;
 cin >> n >> k;
 string s;
 cin >> s;
 int dp[2] = {0 , 0};
 for( int i = 0 , j = 0; i < n; i++ ){
  dp[s[i] - 'a']++;
  if( min( dp[0] , dp[1] ) > k && j <= i ){ // if condition fails
   while( min( dp[0] , dp[1] ) > k ){ // till condition fails
    dp[s[j] - 'a']--;
    j++;
   }
  }
  else{
   ans = max( ans , dp[0] + dp[1] );
  }
 }
 cout << ans;
} 

Way 2 : The Binary Search

Can you imagine that you can solve this problem using a binary search.😵 

When we learn about binary search we think binary search is used only for searching something in sorted data.

But it can do more things that is beyond our imagination. Its a superhero with the ultimate power😎 

Now think how we use binary search for solve this problem.😟

The length of longest substring will in the range [1 , length of string ] , So the possible answer will be in between 1 and length of string both inclusively. 

So our task is to find the most appropriate value in between [1 , length of string ] , here we can use binary search ( this is what binary search made for , we think ). 😬 

For every mid value we have check whether it is possible that the longest substring length be equal to mid value ,  which can be done in O( length of string ) if it is then replace left limit by mid + 1 because it is possible that the answer has greater than mid , but if not then 

replace right limit by mid - 1 because it is not possible that the value of answer will be greater than mid  since condition is not satisfied for mid.

Time Complexity : O( NlogN )

Code:

bool check( string s , int k , int l ){
 int dp[2] = {0 , 0};
 for( int i = 0; i < l; i++ ){
  dp[s[i] - 'a']++;
 }
 if( k >= min( dp[0] , dp[1] ) )return 1; // if possible 
 for( int i = 0; i + l < (int)s.size(); i++ ){
  dp[s[i] - 'a']--;
  dp[s[i + l] - 'a']++;
  if( k >= min( dp[0] , dp[1] ) )return 1; // if possible
 }
 return 0; // not possible
}

int main(){
 int n , k;
 cin >> n >> k;
 string s;
 cin >> s;
 int l = 1 , r = n;
 int ans = 0;
 while( l <= r ){
  int mid = (l + r ) >> 1;
  if( check(s , k , mid ) ){ // check for every mid value
   ans = max( ans , mid );
   l = mid + 1;
  }
  else{
   r = mid - 1;
  }
 }
 cout << ans;
} 

Source of question.