~/leetcode $ 424. Longest-Repeating-Character-Replacement

This problem hard, I don’t like… We can swap at most k letters. Therefore, we can keep track of a sliding window where we keep track of the frequency of each element in the array. Let’s say the top frequency element has a frequency of n and the sum of all other element frequency is m. Then, as long as m <= k then the total length is n + k. If the frequeny of m is greater than k, then we need to make the window smaller until m <= k. We just keep updating the max length until we hit the end of the list.

For this solution, the most computationally expensive part would be keeping track of all the frequencies and updating the top frequency element when it changes.

class Solution {
public:
    int characterReplacement(string s, int k) {
        int left = 0;
        char most_frequent_char = s[0];
        int most_freq = 1;
        unordered_map<char, int> freqs {};
        freqs[s[0]] = 1;
        int result = 1;

        for (int right = 1; right < s.length(); ++right) {
            ++freqs[s[right]];
            if (s[right] == most_frequent_char) {
                ++most_freq;
            }

            // update top if necessary
            if (s[right] != most_frequent_char && freqs[s[right]] > most_freq) {
                most_frequent_char = s[right];
                most_freq = freqs[s[right]];
            }

            // shrink window if necessary
            while ((right - left + 1) - most_freq > k) {
                --freqs[s[left]];
                if (s[left] == most_frequent_char) {
                    // handle - need to get the new most frequent if it changed
                    char new_freq_char = most_frequent_char;
                    int max_freq = freqs[s[left]];
                    for (auto& [first, second]: freqs) {
                        if (second > max_freq) {
                            new_freq_char = first;
                            max_freq = second;
                        }
                    }
                    most_frequent_char = new_freq_char;
                    most_freq = max_freq;
                }
                ++left;
            }

            // update
            result = max(result, right - left + 1);
        }

        return result;
    }
};

After looking around, I found this solution which is super elegant. If we only shrink the window by one every time we see that the current window is ‘invalid’, then we can guarantee that the max length of the valid window is always going to be s.length - left.

class Solution {
public:
    int characterReplacement(string s, int k) {
        int max_count = 0;
        int left = 0;
        unordered_map<char, int> freq {};

        for (int right = 0; right < s.length(); ++right) {
            ++freq[s[right]];
            max_count = max(max_count, freq[s[right]]);

            if (right - left + 1 - max_count > k) {
                --freq[s[left++]];
            }
        }

        return s.length() - left;
    }
};

Time Complexity: O(n)

Space Complexity: O(n)

Time Taken: 26m 20s