Longest Substring with At Most K Distinct Characters

Intuition

The set of distinct characters inside the window only grows when the right edge adds a brand-new character and only shrinks when the left edge drops the last copy of a character. By keeping counts in a map, the size of that map is exactly the distinct count. Whenever it overshoots k, moving the left edge forward and deleting exhausted entries restores a legal window, and the largest legal width seen along the way is the answer.

Algorithm walkthrough

1. 1Maintain a map of character to count for the current window and a left pointer at the start.
2. 2Advance the right pointer, incrementing the count of the incoming character.
3. 3While the map holds more than k distinct keys, decrement the left character's count and remove it from the map when it reaches zero, moving left forward.
4. 4After each adjustment, update the best length with the current window width.
5. 5Return the best width found, which is zero when k is zero.

Implementation

class Solution:
    def lengthOfLongestSubstringKDistinct(self, s: str, k: int) -> int:
        if k == 0:
            return 0
        count = {}
        left = 0
        best = 0
        for right, ch in enumerate(s):
            count[ch] = count.get(ch, 0) + 1
            while len(count) > k:
                lc = s[left]
                count[lc] -= 1
                if count[lc] == 0:
                    del count[lc]
                left += 1
            best = max(best, right - left + 1)
        return best