Getting everything ready for you…

Loading courses, problems and your progress. This takes just a moment.

0s

Practice › Sliding Window

Longest Repeating Character Replacement

Medium · Sliding Window · Asked at Google, Amazon, Microsoft, Uber

You may change at most k characters of the string to any other uppercase letter. Print the length of the longest substring containing a single repeated letter that you can obtain.

Input

First line: s (uppercase letters). Second line: k.

Output

The maximum length.

Constraints

A window is valid if (window length − count of its most frequent letter) ≤ k.

Example 1

Input

ABAB
2

Output

4

Example 2

Input

AABABBA
1

Output

4

Hints

  1. In a window, keep the most frequent letter and replace all the others. That costs (length − maxCount) changes.
  2. Grow the window; if the cost exceeds k, move the left end one step. maxCount never needs to decrease — a smaller value can never give a longer answer.

Approach

Count letters inside the window and track maxCount, the highest count seen. When (r − l + 1) − maxCount > k, slide the left end by one (the window never shrinks below the best length found so far). Not lowering maxCount is safe: the answer only improves when a window with a larger maxCount appears, so the final window length is the answer.

Complexity: O(n) time · O(26) space

Solution

C++ solution

#include <bits/stdc++.h>
using namespace std;

int main() {
    string s;
    int k;
    cin >> s >> k;
    int cnt[26] = {0}, l = 0, mx = 0, best = 0;
    for (int r = 0; r < (int)s.size(); r++) {
        mx = max(mx, ++cnt[s[r] - 'A']);
        if (r - l + 1 - mx > k) cnt[s[l++] - 'A']--;
        best = max(best, r - l + 1);
    }
    cout << best << "\n";
    return 0;
}

Python solution

import sys

data = sys.stdin.read().split()
s, k = data[0], int(data[1])
cnt = [0] * 26
l = mx = best = 0
for r, c in enumerate(s):
    cnt[ord(c) - 65] += 1
    mx = max(mx, cnt[ord(c) - 65])
    if r - l + 1 - mx > k:
        cnt[ord(s[l]) - 65] -= 1
        l += 1
    best = max(best, r - l + 1)
print(best)

Java solution

import java.util.*;

public class Main {
    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        String s = sc.next();
        int k = sc.nextInt();
        int[] cnt = new int[26];
        int l = 0, mx = 0, best = 0;
        for (int r = 0; r < s.length(); r++) {
            mx = Math.max(mx, ++cnt[s.charAt(r) - 'A']);
            if (r - l + 1 - mx > k) cnt[s.charAt(l++) - 'A']--;
            best = Math.max(best, r - l + 1);
        }
        System.out.println(best);
    }
}

Solve Longest Repeating Character Replacement online · All practice problems