LC 0340 [M] Longest Substring with At Most K Distinct Characters - ALawliet/algorithms GitHub Wiki
sliding window + char freq hashmap
class Solution:
def lengthOfLongestSubstringKDistinct(self, s: str, k: int) -> int:
freq = Counter()
max_len = 0
l = 0
for r in range(len(s)):
cl, cr = s[l], s[r]
# do, move r
freq[cr] += 1
# exceeds, undo, move l
if len(freq) > k: # if is ok here cause it can only happen once, doesn't need while
freq[cl] -= 1 ; if freq[cl] == 0: del freq[cl]
l += 1
max_len = max(max_len, r - l + 1)
return max_len