Vaasya and Strings

Problem statement

Given a string of 'a's and 'b's of length n, find the maximum length of a substring with consecutive equal letters. You can change at most k characters in the original string. What is the maximum length of the substring?

Constraints

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.

Examples

n = 11, k = 3

S = "abbaabbabab"

Output = 8

Sudo Code

1. Initialize the count, ans, l, r.

2. Loop till r is less than n.

   1. Loop and get the maximum consequetive same element - (s[r] == ch)

   2. Loop and consume the available k's - (s[r] != ch)

   3. Loop and increament and update cound based on value of s[l] - (s[r] != ch)

Note - First perform above steps for a and then b, Get max of both.

Dry Run

Solution

public class vasyaandstrings {
    public static int maxBeauty(String str, int k, char ch) {
        // Step 1. Initialize the count, ans, l, r.
        int count = 0;
        int ans = Integer.MIN_VALUE;
        int l = 0, r = 0;
        Loop till r is less than size of string
        while (r < str.length()) {
            // Step 2.1. Loop and get the maximum consequetive same element - [s[r] == ch]
            while (r < str.length() && str.charAt(r) == ch) {
                ans = Math.max(ans, r - l + 1);
                r++;
            }
            // Step 2.2. Loop and consume the available k's - [s[r] != ch]
            while (r < str.length() && str.charAt(r) != ch && count < k) {
                count++;
                ans = Math.max(ans, r - l + 1);
                r++;
            }
            // Step 2.3. Loop and increament l and update cound based on value of s[l] - [s[r] != ch] 
            while (l <= r && r < str.length() && str.charAt(r) != ch && count >= k) {
                if (k == 0) {
                    l = ++r;
                    break;
                }
                count -= (str.charAt(l) != ch) ? 1 : 0;
                l++;
            }
        }
        return ans;
    }

    public static void main(String[] args) {
        Scanner scanner = new Scanner(System.in);
        int n = scanner.nextInt();
        int k = scanner.nextInt();
        String str = scanner.next();
        int x = maxBeauty(str, k, 'a');
        int y = maxBeauty(str, k, 'b');
        System.out.println(Math.max(x, y));
    }
}

Time complexity Analysis

Time Complexity - O(N)

Space Complexity - O(1)

Topics Covered

Two Pointers

Companies

It's a question asked in codeforces contest, included this because this give a good intuition of two pointer approach.