Longest Repeating Character Replacement

---

Longest Repeating Character Replacement: You are given a string s and an integer k. You can choose any character of the string and change it to any other uppercase English character. You can perform this operation at most k times.

Return the length of the longest substring containing the same letter you can get after performing the above operations.

Example 1:

Input: s = "ABAB", k = 2
Output: 4
Explanation: Replace the two 'A's with two 'B's or vice versa.

---

Example 2:

Input: s = "AABABBA", k = 1
Output: 4
Explanation: Replace the one 'A' in the middle with 'B' and form "AABBBBA".
The substring "BBBB" has the longest repeating letters, which is 4.

---

Constraints:

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

---

Try this Problem on your own or check similar problems:

1. Max Consecutive Ones III
2. Minimum Number of Operations to Make Array Continuous
3. Longest Substring of One Repeating Character

Solution:

Java

public int characterReplacement(String s, int k) {
    int maxLength = 0, maxFreq = 0, i = 0, j = 0;
    int[] cnt = new int[26];

    while(j < s.length()){
        char current = s.charAt(j);
        maxFreq = Math.max(maxFreq, ++cnt[current-'A']);

        if(j - i + 1 - maxFreq > k){
          cnt[s.charAt(i++) - 'A']--;
        }

        maxLength = Math.max(maxLength, j - i + 1);
        ++j;
    }

    return maxLength;
}

JavaScript

/**
 * @param {string} s
 * @param {number} k
 * @return {number}
 */
var characterReplacement = function (s, k) {
  let maxLength = 0;
  let maxFreq = 0;
  let i = 0;
  let j = 0;
  const cnt = new Array(26).fill(0);

  while (j < s.length) {
    const current = s.charAt(j);
    maxFreq = Math.max(maxFreq, ++cnt[current.charCodeAt() - "A".charCodeAt()]);

    if (j - i + 1 - maxFreq > k) {
      cnt[s.charAt(i).charCodeAt() - "A".charCodeAt()]--;
      i++;
    }

    maxLength = Math.max(maxLength, j - i + 1);
    j++;
  }

  return maxLength;
};

Python

class Solution:
    def characterReplacement(self, s: str, k: int) -> int:
        maxLength = 0
        maxFreq = 0
        i = 0
        j = 0
        cnt = [0] * 26

        while j < len(s):
            current = s[j]
            cnt[ord(current) - ord('A')] += 1
            maxFreq = max(maxFreq, cnt[ord(current) - ord('A')])

            if j - i + 1 - maxFreq > k:
                cnt[ord(s[i]) - ord('A')] -= 1
                i += 1

            maxLength = max(maxLength, j - i + 1)
            j += 1

        return maxLength

C++

class Solution {
public:
    int characterReplacement(string s, int k) {
        int maxLength = 0;
        int maxFreq = 0;
        int i = 0;
        int j = 0;
        std::vector<int> cnt(26, 0);

        while (j < s.length()) {
            char current = s[j];
            maxFreq = std::max(maxFreq, ++cnt[current - 'A']);

            if (j - i + 1 - maxFreq > k) {
                cnt[s[i] - 'A']--;
                i++;
            }

            maxLength = std::max(maxLength, j - i + 1);
            j++;
        }

        return maxLength;
    }
};

---

Time/Space Complexity:

• Time Complexity: O(n)
• Space Complexity: O(1)

---

Explanation:

Since we're trying to find the longest string, we will keep on expanding and each iteration we check if we still have a valid window. Note that a valid window in our case is substring which contains at most k different characters than the most frequent one j - i + 1 - maxFreq > k. So, each time we have an invalid window we have to shift our window to the right (move the start of our window), and the length of the window will be the same as the length of previous valid window (in other words we don't decrease the maximum length window we have found). For each valid window we check if it has longer length that our current maxLength. To always keep the reference to character that's most frequent we use maxFreq, and each time we increase the frequency of the current character ++cnt[current-'A'] we check if it is more frequent than our current most frequent character. To track the occurrence since by the problem statement we only have uppercase letters we can map them to range 0..25 by using c - 'A' trick.