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 subs…


This content originally appeared on DEV Community and was authored by codingpineapple

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
};


This content originally appeared on DEV Community and was authored by codingpineapple


Print Share Comment Cite Upload Translate Updates
APA

codingpineapple | Sciencx (2021-06-06T04:38:07+00:00) LeetCode 424. Longest Repeating Character Replacement (javascript solution). Retrieved from https://www.scien.cx/2021/06/06/leetcode-424-longest-repeating-character-replacementjavascript-solution/

MLA
" » LeetCode 424. Longest Repeating Character Replacement (javascript solution)." codingpineapple | Sciencx - Sunday June 6, 2021, https://www.scien.cx/2021/06/06/leetcode-424-longest-repeating-character-replacementjavascript-solution/
HARVARD
codingpineapple | Sciencx Sunday June 6, 2021 » LeetCode 424. Longest Repeating Character Replacement (javascript solution)., viewed ,<https://www.scien.cx/2021/06/06/leetcode-424-longest-repeating-character-replacementjavascript-solution/>
VANCOUVER
codingpineapple | Sciencx - » LeetCode 424. Longest Repeating Character Replacement (javascript solution). [Internet]. [Accessed ]. Available from: https://www.scien.cx/2021/06/06/leetcode-424-longest-repeating-character-replacementjavascript-solution/
CHICAGO
" » LeetCode 424. Longest Repeating Character Replacement (javascript solution)." codingpineapple | Sciencx - Accessed . https://www.scien.cx/2021/06/06/leetcode-424-longest-repeating-character-replacementjavascript-solution/
IEEE
" » LeetCode 424. Longest Repeating Character Replacement (javascript solution)." codingpineapple | Sciencx [Online]. Available: https://www.scien.cx/2021/06/06/leetcode-424-longest-repeating-character-replacementjavascript-solution/. [Accessed: ]
rf:citation
» LeetCode 424. Longest Repeating Character Replacement (javascript solution) | codingpineapple | Sciencx | https://www.scien.cx/2021/06/06/leetcode-424-longest-repeating-character-replacementjavascript-solution/ |

Please log in to upload a file.




There are no updates yet.
Click the Upload button above to add an update.

You must be logged in to translate posts. Please log in or register.