Longest Repeating Character Replacement

Given a string, s, of lowercase English characters and an integer, k, return the length of the longest substring after replacing at most k characters with any other lowercase English character so that all the characters in the substring are the same.

Examples

Sample Example 1

Input:

• s = "aabccbb"
• k = 2

Output: Length of longest substring = 5

Explanation: All the characters of the substring "bccbb" can be the same if we replace all the instances of "c" with "b". The length of this substring is 5, and it is the longest substring, which will consist of the same character after, at most, k replacements.

Sample Example 2

Input:

• s = "fzfzfz"
• k = 6

Output: Length of longest substring = 6

Explanation: All the characters of the substring "fzfzfz" can be the same if we replace all the instances of "z" with "f". The length of this substring is 6, and it is the longest substring, which will consist of the same character after, at most, k replacements. We can achieve the same thing by replacing all the instances of "f" with "z".

Solution One solution I can think of this is If I maintain a Map that store frequency of each character and maintain a count for max occurring character in window. I know maxFreq + k are allowed if at any point I see my windows grows longer then it, I'll short my window and updated longestLength

function longestRepeatingCharacterReplacement(str, k) {
    const charFrequency = new Map();
    let windowStart = 0;
    let maxFrequency = 0;
    let longestLength = 0;

    for (let windowEnd = 0; windowEnd < str.length; windowEnd++) {
        const currentChar = str[windowEnd];
        charFrequency.set(currentChar, (charFrequency.get(currentChar) || 0) + 1);

        maxFrequency = Math.max(charFrequency.get(currentChar), maxFrequency);

        const windowSize = windowEnd - windowStart + 1;
        const charsToReplace = windowSize - maxFrequency;

        if (charsToReplace > k) {
            const startChar = str[windowStart];
            charFrequency.set(startChar, charFrequency.get(startChar) - 1);
            windowStart++;
        }

        longestLength = Math.max(windowEnd - windowStart + 1, longestLength);
    }

    return longestLength;
}

console.log(longestRepeatingCharacterReplacement('aabccbb', 2));

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