Problem

Problem ID: 424

Title: Longest Repeating Character Replacement

Difficulty: Medium

Description:

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.

Thoughts

I found this question extremely hard. Had to view the related topics before being able to derive a non-ideal O(N^2) solution and had to view the discussion to derive the optimal O(N) solution.

The main idea that I missed is that you can determine determine the number of replacement performed in O(1) time by keeping a frequency map. Number of replacement = length of curr substring - highest frequency val. Additionally any map containing characters can be traversed in O(1) time as there are only constant(26) number of keys.

Solution

Checking a valid substring with repeating characters and less than k replacement can be done using: substring_length - max_char_freq <= k.

We can solve this question by maintain a sliding window that always ensure that substring_length - max_char_freq <= k. We do so by advancing the start of the substring whenever there is a violation.

Implementation

class Solution {
public:
    int characterReplacement(string s, int k) {
        unordered_map<char,int> char_freq;
        int n = s.length();
        int start = 0;
        int ans = 0;
        for (int i = 0; i < n; i++) {
            char_freq[s[i]]++;
            int max_count = char_freq[GetMax(char_freq)];
            if (i-start+1 -  max_count> k) {
                 
                char_freq[s[start]]--;
                start++;
            }
            ans = max(ans, i-start +1);
        }
        return ans;
    }
    
    char GetMax(const unordered_map<char,int>& m) {
        int max_val = 0;
        char max_c;
        for (const auto [c, val] : m) {
            if (val > max_val) {
                max_c = c;
                max_val = val;
            }
        }
        return max_c;
    }
};