19. Longest Repeating Character Replacement

MediumString Hash Table Sliding Window

You are given a string s of uppercase English letters and an integer k. You may pick at most k positions in s and change the letter at each of them to any other uppercase letter.

Return the length of the longest substring that can be made to consist of a single repeated letter using those changes.

Example 1

Input: s = "BAAB", k = 1
Output: 3

Explanation: Change the first B to get "AAAB"; its first three letters are all A. Making all four equal would need two changes.

Example 2

Input: s = "XYYXYYY", k = 1
Output: 6

Explanation: Change the X at index 3: "YYYYYY" from index 1 to 6.

Example 3

Input: s = "ABCDE", k = 2
Output: 3

Explanation: Any three neighbouring letters can be made equal with two changes.

Constraints

1 <= s.length <= 10^5
s consists of uppercase English letters
0 <= k <= s.length

💡 Hint 1

A window can be turned into one repeated letter when windowLength - (count of its most frequent letter) <= k.

💡 Hint 2

Slide a window over s with 26 letter counters. Grow it on the right; when it needs more than k changes, shrink it from the left.

💡 Hint 3

You only care about windows longer than the best one so far, so the "most frequent count" never needs to be decreased when the window shrinks.

Try it yourself first ✎

Solutions stick better after a real attempt. Peek when you're ready.

Approach

Use a sliding window with a count of each letter inside it. A window is fixable when its length minus the count of its most frequent letter, the number of letters you would have to change, is at most k. Extend the window to the right one letter at a time, updating maxCount; if the window then needs more than k changes, drop its leftmost letter. maxCount is never lowered: the window only has to beat the best length found so far, and that requires a higher maxCount anyway. The window length at the end of each step is a candidate answer.

Time O(n)Space O(1) (26 counters)

function characterReplacement(s, k) {
  const count = new Array(26).fill(0);
  let left = 0;
  let maxCount = 0;
  let best = 0;
  for (let right = 0; right < s.length; right++) {
    const c = s.charCodeAt(right) - 65;
    count[c]++;
    maxCount = Math.max(maxCount, count[c]);
    while (right - left + 1 - maxCount > k) {
      count[s.charCodeAt(left) - 65]--;
      left++;
    }
    best = Math.max(best, right - left + 1);
  }
  return best;
}

class Solution {
    public int characterReplacement(String s, int k) {
        int[] count = new int[26];
        int left = 0, maxCount = 0, best = 0;
        for (int right = 0; right < s.length(); right++) {
            int c = s.charAt(right) - 'A';
            count[c]++;
            maxCount = Math.max(maxCount, count[c]);
            while (right - left + 1 - maxCount > k) {
                count[s.charAt(left) - 'A']--;
                left++;
            }
            best = Math.max(best, right - left + 1);
        }
        return best;
    }
}

/**
 * @param {string} s
 * @param {number} k
 * @return {number}
 */
function characterReplacement(s, k) {

}

Ctrl/⌘ + ' run · Ctrl/⌘ + Enter submit