Finding maximum length of continuous string which has same characters

I'm solving this problem from codeforces. I've a solution which has complexity of O(n²). But the time limit exceeds on some of the test cases. The problem statement is:


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


Sample Input/Output:


8 1


aabaabaa


Output


5

My solution is:

import java.util.Scanner;
public class CF676C {
public static void main(String args[]){
    Scanner in = new Scanner(System.in);
    int n = in.nextInt(), max = in.nextInt(),a=0,b=0;

    String s = in.next();
    int i,j;
    for(i=0;itemp)
        {
            temp=count;
        }
    }
    System.out.println(temp);
}
}

I can't understand how to reduce time taken by the code. Is there any other solution or approach available?

Yes, you can tackle this problem is a much faster way, with an O(n) algorithm, using a left and a right pointer delimiting the substrings to consider.

For each character in the input String, the idea is to keep an array counting the number of 'a' and 'b' between a given left pointer, that will represent the start of the substring, and the current character.

When the count of each 'a' or of each 'b' is less than the allowed number of characters to change, we can consider making the change and incrementing the answer. Then, when both of those 2 counts becomes greater than the allowed number of characters to change, it means we cannot change more characters so we hit a maximum length: the left pointer is increased, and the count of the character at that pointer is decreased.

The count of 'a' and 'b' characters can be modeled as an integer array (index 0 corresponds to the count of 'a' while index 1 corresponds to the count of 'b').

Scanner in = new Scanner(System.in);
int n = in.nextInt(), max = in.nextInt();
String s = in.next();

int left = 0, answer = 0;
int[] count = { 0, 0 };
for (char c : s.toCharArray()) {
    count[c - 'a']++;
    if (Math.min(count[0], count[1]) > max) {
        count[s.charAt(left) - 'a']--;
        left++;
    } else {
        answer++;
    }
}
System.out.println(answer);

This approach passes all the tests of the challenge.

StackExchange Code Review Q#140840, answer score: 7