DEV Community

codingpineapple
codingpineapple

Posted on

LeetCode 424. Longest Repeating Character Replacement (javascript solution)

Description:

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.

Solution:

Time Complexity : O(n)
Space Complexity: O(n)

var characterReplacement = function(s, k) {
    // Keep count of all the characters in the string
    const chars = {}
    // left pointer, character with the current max frequency, return value
    let left = 0, maxf = 0, output = 0
    for(let right = 0; right < s.length; right++) {
        const char = s[right]
        // Increment count of the current character
        chars[char] = 1 + (chars[char] || 0)
        // Update the character frequency
        maxf = Math.max(maxf, chars[char])
        // Shrink the window of characters we are looking at until we can have a window of all the same characters + k charcters to change
        while((right-left+1) - maxf > k) {
                chars[s[left]] -= 1
                left++
          }
        // Update the output if the current window is greater than our previous max window
        output = Math.max(output, right - left +1)
    }
    return output
};
Enter fullscreen mode Exit fullscreen mode

Top comments (0)