LeetCode 424. Longest Repeating Character Replacement

Solving LeetCode 424. Longest Repeating Character Replacement, with a Sliding Window approach. Click here to try it out your self!

LeetCode Problem Statement

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

Examples:

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

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.

This was a tough problem for me to wrap my head around. The key for me was getting a better insight into what I was looking for…

Working backwards, what does our solution look like?

We are looking for the longest substring that contains the same characters after substituting up to K times.

In other words we are looking for a substring that contains the max alike letters plus K substitutions. So in any given window our answer should work out to be:

const solution = maxLetterCountInWindow + k

Where solution must be less than the length of the string.

Example 1:

Input: s = "ABAB", k = 2
Output: 4

window = {A: 2, B: 2} from index 0 to 3;
maxLetterCount = 2;
k = 2;

solution = maxLetterCount + k
solution = 4

In the above example we can either have a window where the maxLetter is A, or B. In either case we can delete the other letter up to K times, which in this case is 2.

Example 2:

Input: s = "AABABBA", k = 1
Output: 4

Solution 1
window = {A: 3, B: 1} from index 0 to 3
maxLetterCount = 3
k = 1

solution = maxLetterCount + k
solution = 4

Solution 2
window = {A: 1, B: 3} fro index 2 to 5
maxLetterCount = 3
k = 1

solution = maxLetterCount + k
solution = 4

Understanding this insight turned this hard problem into a manageable one. Let’s look at the code and see how we can apply this.

Code

const findLengthOfLongestSubStringWithMaxDeletes = (str, k) => {

    let maxLength = -Infinity;
    let maxLetterCount = 0; 
    let frequencyMap = {}; // for the given window
    let windowStart = 0;

    for(let windowEnd = 0; windowEnd < s.length; windowEnd++) {
        let rightChar = s[windowEnd];
        if (!frequencyMap[rightChar]) {
            frequencyMap[rightChar] = 0;
        }

        // Keep track of the char frequency in the currentWindow
        frequencyMap[rightChar] += 1;

        // Update the maxLetterCount for the window
        maxLetterCount = Math.max(maxLetterCount, frequencyMap[rightChar]); 

        // Validate the current window to make sure we satisfy the constraints 
        // If the currentLength - maxLetterCount > k 
        // shrink the window since we don't have substitutions left. 
        const currentLength = windowEnd - windowStart + 1;
        if ((currentLength - maxLetterCount) > k) {
            let leftChar = s[windowStart];
            // Remember to decrement the frequencyMap with the character 
            // that is going out of the window
            frequencyMap[leftChar] -= 1;
            windowStart++;
        }

        // Now we have a valid window, so check if we have 
        // found a better answer
        const validLength = windowEnd - windowStart + 1;
        maxLength = Math.max(validLength, maxLength);
    }

    return maxLength;
}

Summary

This algorithm runs in O(n) time and O(1) space. Given that we only have 26 letters in the english language, that’s a fixed space we would keep in the hashmap which is equivalent to O(1).

I struggled when solving this problem. Understanding that the length of the substring would equal the maxNumberOfCharacters + k, was the key insight I needed to make a break through.

Hope you found this helpful!