41 - Longest Repeating Character Replacement

LeetCode challenge: Longest Repeating Character Replacement

Shoutout to Shenai for pairing on this with me! We had just done Longest Substring Without Repeating Characters so this seemed like a logical next step.

function characterReplacement(s: string, k: number): number {
    // If string is empty or k is negative, return 0
    if (!s || k < 0) return 0;
    
    // Create a frequency map for characters in the current window
    const freq: Map<string, number> = new Map();
    
    let maxLength = 0;        // Track the max valid window length
    let maxFreq = 0;         // Track the highest frequency in current window
    let windowStart = 0;     // Left pointer of the window
    
    // Iterate through the string with right pointer
    for (let windowEnd = 0; windowEnd < s.length; windowEnd++) {
        // Update frequency of current character
        const currentChar = s[windowEnd];
        freq.set(currentChar, (freq.get(currentChar) || 0) + 1);
        
        // Update maxFreq if current char frequency is higher
        maxFreq = Math.max(maxFreq, freq.get(currentChar)!);
        
        // Calculate number of characters to be replaced in current window
        const windowLength = windowEnd - windowStart + 1;
        const charsToReplace = windowLength - maxFreq;
        
        // If we need more replacements than k allows, shrink window
        if (charsToReplace > k) {
            // Decrease frequency of char at windowStart
            const startChar = s[windowStart];
            freq.set(startChar, freq.get(startChar)! - 1);
            windowStart++;
        }
        
        // Update maxLength with current valid window length
        maxLength = Math.max(maxLength, windowEnd - windowStart + 1);
    }
    
    return maxLength;
}

Shenai showed me this cool thing where, when starting a leetcode problem, she diagrammed it out first so I tried a little of that. I tried doing that here, on excalidraw, which was really helpful. But this didn’t quite do justice to the motion of it. So I made an animation: It was super fun, so I made another one…I imagined that instead of being a rigid thing, the window was just this flexible, expanding and contracting worm-like organism that was able to extract nutrients out of these continuous ranges of same-characters, with maybe some sort of metabolic budget of being able to withstand some level of interruption (k):

P.S. It actually looks like I have tried tackling this one before at 30) Longest Repeating Character Replacement. It looks like tried writing out a short story to understand it, but I don’t think it helped as much as this more motion-based understanding.

That was fun too though! Funny how this problem consistently inspires/forces me to find more creative ways of grokking when others haven’t.

Returning Again

A lot of my work before paid off - a lot of these concepts are fresh in my brain. Diving back in and this time reflecting on the O(n * 26) (which is yes, still technically O(n))) approach since I hadn’t really considered it before and it has some cool quirks in syntax.

This is what I got this time in 8:39

A few stumbles:

• I forget that although I don’t need to decrement maxFreq I do need to decrement my hashmap
• I briefly forgot to get the max of res, and just overwrote res without thinking

function characterReplacement(s: string, k: number): number {
    let l = 0
    let count = {}
    let maxFreq = 0
    let res = 0
 
    for (let r = 0; r < s.length; r++){
        count[s[r]] = (count[s[r]] ?? 0) + 1
 
        maxFreq = Math.max(maxFreq, count[s[r]])
        while (r - l + 1 - maxFreq > k ){
            count[s[l]] = (count[s[l]]) - 1
            l++
        }
        
        res = Math.max(res, r - l + 1)
 
    }
    return res
};

Okay got it in 1:55 now. That’s the power of spaced repition.