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

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/
Please log in to upload a file.
There are no updates yet.
Click the Upload button above to add an update.