44 lines
1.2 KiB
Python
44 lines
1.2 KiB
Python
|
# Time: O(N)
|
||
|
|
# Space: O(N)
|
||
|
|
|
||
|
|
from collections import Counter
|
||
|
|
|
||
|
|
class Solution:
|
||
|
|
def characterReplacement(self, s: str, k: int) -> int:
|
||
|
|
'''
|
||
|
|
Sliding window approach, optimized
|
||
|
|
'''
|
||
|
|
|
||
|
|
def window_size(l, r):
|
||
|
|
return r - l + 1
|
||
|
|
|
||
|
|
# Need to keep track of frequency of each character in the
|
||
|
|
# window
|
||
|
|
count = Counter()
|
||
|
|
|
||
|
|
# We can optimize the prev sliding window approach by just keeping
|
||
|
|
# track of maximum frequency/count of an element we've seen so far.
|
||
|
|
maxf = 0
|
||
|
|
|
||
|
|
l = r = 0
|
||
|
|
result = 0
|
||
|
|
|
||
|
|
while r < len(s):
|
||
|
|
# Increment the frequency of the `r`th char
|
||
|
|
count.update(s[r])
|
||
|
|
|
||
|
|
# If right's frequency is bigger, make it the new
|
||
|
|
# max frequency
|
||
|
|
maxf = max(maxf, count[s[r]])
|
||
|
|
|
||
|
|
# Refer to neetcode: https://www.youtube.com/watch?v=gqXU1UyA8pk
|
||
|
|
# TODO: Document this approach my own way
|
||
|
|
if window_size(l, r) - maxf > k:
|
||
|
|
count.subtract(s[l])
|
||
|
|
l += 1
|
||
|
|
|
||
|
|
result = max(result, window_size(l, r))
|
||
|
|
r += 1
|
||
|
|
|
||
|
|
return result
|