Longest Repeating Character Replacement

Problem

You are given a string s consisting of only uppercase English characters and an integer k. You can choose up to k characters of the string and replace them with any other uppercase English character.

After performing at most k replacements, return the length of the longest substring which contains only one distinct character.

Examples

Example 1:

Input: s = "XYYX", k = 2

Output: 4

Explanation: Either replace the ‘X’s with ‘Y’s, or replace the ‘Y’s with ‘X’s.

Example 2:

Input: s = "AAABABB", k = 1

Output: 5

Constraints

• 1 <= s.length <= 1000
• 0 <= k <= s.length

You should aim for a solution with O(n) time and O(m) space, where n is the length of the given string and m is the number of unique characters in the string.

Solution

We walk a sliding window [left, right] along the string. Every loop moves the right end forward. We increment the frequency of the new char seen. If the sliding window is not valid, move the left end forward and update frequencies. By valid, we are checking if the size of the window is larger than the difference between K and the max frequency char in the window (otherwise too many of them to swap). Then we check for a new max.

class Solution {
public:
    int characterReplacement(const std::string &s, int k) {
        std::unordered_map<char, int> frequencies;
        int max_str = 0;
        // Walk sliding window along string
        // Right is the right boundary
        // If the difference in length - max_freq > k, then we need to move window left
        //  until this condition is satisfied
        std::size_t left = 0;
        int max_freq = 0;
        for (std::size_t right = 0; right < s.size(); ++right) {
            ++frequencies[s[right]];
            max_freq = std::max(max_freq, frequencies[s[right]]);
            // If sliding window is not valid, make it valid.
            // Technically we would need to recalculate max_freq when moving left,
            // because max_freq may no longer be the true max frequency in the current window.
            // However, max_freq is allowed to be stale: it only ever overestimates the
            // current max frequency. This may let us temporarily keep an invalid window,
            // but it cannot increase the answer incorrectly, since any stale max_freq value
            // came from an earlier window where that frequency really existed.
            while ((right - left + 1) - max_freq > k) {
                --frequencies[s[left]];
                ++left;
            }
            max_str = std::max(max_str, static_cast<int>(right - left) + 1);
        }
        return max_str;
    }
};