Learning Journal

3/10/2024

Longest Repeating Character Replacement - a faster approach

Tags: algorithms leetcode sliding_window

function characterReplacement(s: string, k: number): number {
    const hashTB:Record<string,number> = {};
    let start = 0, maxFreq = 0, maxLength = 0;

    for(let end = 0; end < s.length; end++) {
        if(!hashTB[s[end]]) hashTB[s[end]] = 1;
        else hashTB[s[end]]++;

        const curLength = end - start + 1;
        if(maxFreq < hashTB[s[end]]) {
            maxFreq = hashTB[s[end]];
        }

        if(curLength - maxFreq > k) {
            hashTB[s[start++]]--;
        }
        else if (maxLength < curLength) {
            maxLength = curLength;
        }
    }

    return maxLength;
};function characterReplacement(s: string, k: number): number {
    const hashTB:Record<string,number> = {};
    let start = 0, maxFreq = 0, maxLength = 0;

    for(let end = 0; end < s.length; end++) {
        if(!hashTB[s[end]]) hashTB[s[end]] = 1;
        else hashTB[s[end]]++;

        const curLength = end - start + 1;
        if(maxFreq < hashTB[s[end]]) {
            maxFreq = hashTB[s[end]];
        }

        if(curLength - maxFreq > k) {
            hashTB[s[start++]]--;
        }
        else if (maxLength < curLength) {
            maxLength = curLength;
        }
    }

    return maxLength;
};

THE PROBLEM

So, let me trying to understand how exactly my code works. When the window’s size reaches the maximum length, the algorithm will maintain its length by advancing start pointer at each iteration. At this point forward, when end advances, the only character that has the possibility of increasing is the character pointed to by end. So, if there is ever a new maxFreq’s value, it will be at hashTB[s[end]because it is the only value that is increasing. Other value will decrease when advancing start pointer. So, we only need to compare the maxFreq with hashTB[s[end]]`.

Revised by ChatGPT

The algorithm maintains the maximum length of the window by advancing the start pointer whenever necessary. Once the window reaches its maximum size, it will retain this size for subsequent iterations. From this point forward, as the end pointer advances, the only character frequency that has the potential to increase is the one pointed to by end. Consequenty, if there is ever a new maximum frequency (maxFreq), it will be reflected in hashTB[s[end]], as it is the only value that increases. In contrast, other character frequencies will decrease when the start pointer advances. Therefore, it suffices to compare maxFreq with hashTB[s[end]] to determine if there's a new maximum frequency.