Finding maximum length of continuous string which has same characters

Question

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;i<n;i++){
        if(s.charAt(i) == 'a'){
            ++a;
        }
        else{
            ++b;
        }
    }
    char z;
    if(a<=b){
        z='a';
    }
    else{
        z='b';
    }
    int max1;
    int count=0;
    int temp=0;
    for(i=0;i<s.length();i++)
    {
        max1=max;
        count=0;
        for(j=i;j<s.length()&&max1!=-1;j++)
        {
            if(s.charAt(j)==z&&max1!=-1)
            {
                max1--;
            }
            if(max1!=-1)
            {
                count++;
            }
        }
        if(count>temp)
        {
            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?

Answer 1

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.

Answer 2

At the moment, the entirety of the solution is in your main method. More often than not, in OOP, your main method should be reserved to be the entry point of your program only, rather than the entire program. This helps to keep your code better organized, and easier to understand and maintain.

In this particular case, I would move the code that actually solves the problem to another class, to help make it more general, and just read the input and print the output in main.

---

There a few naming concerns that stood out. First, the problem states the input numbers are n and k, which are often used for mathematical notation as a matter of convention; however, those don't necessarily translate well to code, as code should preferably be written in such a way that it makes the intentions clear.

First, I would change the input variable names like so:

• n to strLength
• max (or, k in the problem) to maxCharChangesAllowed
• s (the input string of As and Bs) to targetStr (or something similar)

Moving them to a static method signature in a new class would look like this:

class CodeForce676C {
    public static int solve(int strLength, int maxCharChangesAllowed, String targetStr) {
        // ...
    }
}

---

Similarly, a, b are not very clear, I would suggest countOfA and countOfB. We will extract that logic to a separate method as well. We can eliminate your char z and just return the result directly from the method. We can also simplify the return by using Java's ternary operator instead of if-then-else structure.

We can also leverage the fact that the length of the string is provided as input, and save ourselves a String.length() calculation.

Note that declaring int i, j iteration counters outside of the loop signature is not recommended, unless you are using those variables for something besides the loop itself (which you are not). The compiler will know that i won't be needed after the loop is exited so it can just remove it then, and if you have another loop in the same method that also uses i it will just make a new one.

private static char findCharWithLeastFrequency(String targetStr, int strLength) {
    int countOfA = 0;
    int countOfB = 0;
    for (int i = 0; i < strLength; i++) {
        targetStr.charAt(i) == 'a' ? ++countOfA : ++countOfB;
        if (targetStr.charAt(i) == 'a') {
            ++countOfA;
        } else {
            ++countOfB;
        }
    }
    return countOfA <= countOfB ? 'a' : 'b';
}

---

Likewise we could also move the other part of the logic (that uses max1 and count) to its own method. I renamed max1 to changesRemaining, count to charCount, and temp to substringLength. The algorithm itself was already addressed in Tunaki's answer, so I simply adapted your existing algorithm to make the code easier to understand and cleaner.

Here is a working demo on repl.it. To run the given test case, run it and type in the console: 8 1 aabaabaa

---

import java.util.Scanner;

class Main {
    public static void main(String args[]) {
        Scanner in = new Scanner(System.in);
        // Read the values from the input
        int n = in.nextInt();
        int k = in.nextInt(); 
        String s = in.next();
        // Solve the calculation and print the result to console:
        System.out.println(CodeForce676C.solve(n, k, s));
    }
}

class CodeForce676C {

    public static int solve(int strLength, int maxCharChangesAllowed, String targetStr) {
        char leastFrequentChar = findCharWithLeastFrequency(targetStr, strLength);
        return getLengthOfLongestPossibleSubstring(
                targetStr, 
                maxCharChangesAllowed, 
                leastFrequentChar, 
                strLength);
    }

    private static char findCharWithLeastFrequency(String targetStr, int strLength) {
        int countOfA = 0;
        int countOfB = 0;
        for (int i = 0; i < strLength; i++) {
            if (targetStr.charAt(i) == 'a') {
                ++countOfA;
            } else {
                ++countOfB;
            }
        }
        return countOfA <= countOfB ? 'a' : 'b';
    }

    private static int getLengthOfLongestPossibleSubstring(
            String targetStr, 
            int maxCharChangesAllowed, 
            char leastFrequentChar,
            int strLength) {
        int changesRemaining;
        int charCount = 0;
        int substringLength = 0;
        for (int i = 0; i < strLength; i++) {
            // Reset values on each outer iteration
            changesRemaining = maxCharChangesAllowed;
            charCount = 0;
            for (int j = i; j < strLength && changesRemaining != -1; j++) {
                if (targetStr.charAt(j) == leastFrequentChar && changesRemaining != -1) {
                    changesRemaining--;
                }
                if (changesRemaining != -1) {
                    charCount++;
                }
            }
            if(charCount > substringLength) {
                substringLength = charCount;
            }
        }
        return substringLength;
    }
}