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