Sliding Window Pattern

Longest Repeating Character Replacement

So far, you’ve probably brainstormed some approaches and have an idea of how to solve this problem. This problem can be solved using Sliding Window pattern. Let’s explore...

Solution: Using Sliding Window

Step 0

This is our initial setup.

Step 1

Initially, windowStart and windowEnd points to index 0. Add the first character in the frequencyMap and initialise its frequency by 1. Set the length of max substring equal to 1 i.e. maxLength = 1 because the current window size size is 1, which is the longest so far, and move on to the next iteration.

Step 2

Again, the windowEnd pointer is pointing to character 'a', so increment the frequency of character 'a' in the frequencyMap, and update the maxFrequency variable. Set maxLength equal to 2 because the current window is the longest so far with size 2, and move on to the next iteration.

Step 3

Here, the windowEnd pointer is pointing to character 'b' and it is not present in the frequencyMap, so add it in the hash map and initialise its frequency to 1. The maxFrequency is still 2, which makes the number of required replacements in the current window 1 (windowEnd - windowStart + 1 - maxFrequency). Therefore, this window is the longest so far with same characters after replacement, so update the maxLength with the current window size, which is 3 now, and move on to the next iteration.

Step 4

Here, the windowEnd pointer is pointing to character 'c' and it is not present in the frequencyMap, so add it in the hash map and initialise its frequency by 1. The maxFrequency is still 2, which makes the number of required replacements in the current window 2. Therefore, this window is the longest so far with same characters after replacement, so update maxLength with the current window size, which is 4 now, and move on to the next iteration.

Step 5

Now, the windowEnd pointer is pointing to character 'c', so increment its frequency by 1. The maxFrequency is still 2, but the number of replacements in this window have exceeded the limit of k = 2. So, slide (shrink) the window forward by incrementing the windowStart pointer by 1.

Step 6

Now, the windowStart pointer has been incremented by 1, and subsequently, the frequency of 'a' is decremented by 1 in the frequencyMap. Here, the window size is equal to length of max substring. So, move on to the next iteration.

Step 7

Now, the windowEnd pointer is pointing to character 'b', so increment its frequency by 1. The maxFrequency is still 2 but, the number of replacements in this window have exceeded the limit of k = 2. So, slide (shrink) the window forward by incrementing the windowStart pointer by 1.

Step 8

Step 9

Now, the windowEnd pointer is pointing to character 'b', so increment its frequency by 1. The maxFrequency is now 3, so the required replacements in this window are 2. This window is the longest so far with the same characters after replacements, so update the length of max substring variable with the current window size i.e. maxLength = 5 now. Since the windowEnd pointer is pointing to the last character of the input string, return the length of max substring.

Let's look at the code now.

Java Code

class Solution {
    public int characterReplacement(String s, int k) {
        int windowStart = 0;
        int maxLength = 0;
        Map<Character, Integer> frequencyMap = new HashMap<>();
        int maxFrequency = 0;

        for(int windowEnd = 0; windowEnd < s.length(); windowEnd++) {
            char ch = s.charAt(windowEnd);
            frequencyMap.put(ch, frequencyMap.getOrDefault(ch, 0) + 1);
            maxFrequency = Math.max(maxFrequency, frequencyMap.get(ch));
            while(windowEnd - windowStart + 1 - maxFrequency > k) {
                char leftChar = s.charAt(windowStart);
                frequencyMap.put(leftChar, frequencyMap.get(leftChar) - 1);
                windowStart += 1;
            }

            maxLength = windowEnd - windowStart + 1;
        }
        return maxLength;
    }
}

C++ Code

class Solution {
public:
    int characterReplacement(string s, int k) {
        int windowStart = 0;
        int maxLength = 0;
        int maxFrequency = 0;
        unordered_map<char, int> frequencyMap;

        for(int windowEnd = 0; windowEnd < s.length(); windowEnd++) {
            char ch = s[windowEnd];
            frequencyMap[ch] += 1;
            maxFrequency = max(maxFrequency, frequencyMap[ch]);
            while(windowEnd - windowStart + 1 - maxFrequency > k) {
                char leftChar = s[windowStart];
                frequencyMap[leftChar] -= 1;
                windowStart += 1;
            }

            maxLength = max(maxLength, windowEnd - windowStart + 1);
        }
        return maxLength;
    }
};

Python Code

class Solution:
    def characterReplacement(self, s: str, k: int) -> int:
        window_start = 0
        max_length = 0
        max_frequency = 0
        frequency_map = dict()

        for  window_end in range(len(s)):
            ch = s[window_end]
            frequency_map[ch] = frequency_map.get(ch, 0) + 1
            max_frequency = max(max_frequency, frequency_map[ch])
            while window_end - window_start + 1 - max_frequency > k:
                left_char = s[window_start]
                frequency_map[left_char] -= 1
                window_start += 1

            max_length = max(max_length, window_end - window_start + 1)

        return max_length

Complexity Analysis

Time Complexity: The time complexity of the solution is O(n), where n is the length of the input string because we iterate over the input string only once.

Space Complexity: The space complexity of the solution is O(1), since we will be storing the frequency of 26 characters at most in the hash map.

Prefix Sum