1. Binary Search + Fixed Size Sliding Window

Intuition

The answer has a monotonic property: if we can find a valid substring of length L, then there must also exist valid substrings of all lengths less than L. This makes binary search applicable. We binary search on the answer length and for each candidate length, use a fixed-size sliding window to check if any window of that size has at most k distinct characters.

Algorithm

1. If k >= n, return n (entire string is valid).
2. Binary search on the answer with left = k and right = n.
3. For each midpoint mid, check if a valid window of size mid exists:
   • Use a hash map to count characters in the initial window.
   • Slide the window across the string, adding the new character and removing the old one.
   • If at any point the distinct count is at most k, return true.
4. Based on the result, narrow the search range.
5. Return left as the final answer.

class Solution:
    def lengthOfLongestSubstringKDistinct(self, s: str, k: int) -> int:
        n = len(s)
        if k >= n:
            return n
        left, right = k, n
        
        def isValid(size):
            counter = collections.Counter(s[:size])
            if len(counter) <= k:
                return True
            for i in range(size, n):
                counter[s[i]] += 1
                counter[s[i - size]] -= 1
                if counter[s[i - size]] == 0:
                    del counter[s[i - size]]
                if len(counter) <= k:
                    return True
            return False
        
        while left < right:
            mid = (left + right + 1) // 2
            
            if isValid(mid):
                left = mid
            else:
                right = mid - 1
        
        return left

Time & Space Complexity

• Time complexity: $O(n \cdot \log n)$
• Space complexity: $O(n)$

Where $n$ is the length of the input string s and $k$ is the maximum number of distinct characters.

---

2. Sliding Window

Intuition

A variable-size sliding window is the natural fit for this problem. We expand the window by moving the right pointer and adding characters. When we exceed k distinct characters, we shrink the window from the left until we're back to at most k distinct characters. The maximum window size seen during this process is our answer.

Algorithm

1. Initialize left = 0, maxSize = 0, and a hash map counter to track character frequencies.
2. For each right from 0 to n-1:
   • Add s[right] to the counter.
   • While the number of distinct characters exceeds k:
     • Decrement the count of s[left].
     • If the count becomes 0, remove it from the map.
     • Increment left.
   • Update maxSize = max(maxSize, right - left + 1).
3. Return maxSize.

class Solution:
    def lengthOfLongestSubstringKDistinct(self, s: str, k: int) -> int:
        n = len(s)
        max_size = 0
        counter = collections.Counter()
        
        left = 0
        for right in range(n):
            counter[s[right]] += 1
            
            while len(counter) > k: 
                counter[s[left]] -= 1
                if counter[s[left]] == 0:
                    del counter[s[left]]
                left += 1
            
            max_size = max(max_size, right - left + 1)
                    
        return max_size

Time & Space Complexity

• Time complexity: $O(n)$
• Space complexity: $O(k)$

Where $n$ is the length of the input string s and $k$ is the maximum number of distinct characters.

---

3. Sliding Window II

Intuition

An optimization on the standard sliding window: instead of shrinking the window with a while loop, we only shrink by one step when invalid. This keeps the window size from ever decreasing by more than one, which means we only need to track when the window grows. The final answer is the maximum window size achieved, which equals n - left at the end.

Algorithm

1. Initialize maxSize = 0 and a hash map counter.
2. For each right from 0 to n-1:
   • Add s[right] to the counter.
   • If distinct characters exceed k:
     • Decrement count of s[right - maxSize] (the leftmost character of current max window).
     • Remove from map if count is 0.
   • Otherwise, increment maxSize.
3. Return maxSize.

class Solution:
    def lengthOfLongestSubstringKDistinct(self, s: str, k: int) -> int:
        max_size = 0
        counter = collections.Counter()
        
        for right in range(len(s)):
            counter[s[right]] += 1
            
            if len(counter) <= k:
                max_size += 1
            else:
                counter[s[right - max_size]] -= 1
                if counter[s[right - max_size]] == 0:
                    del counter[s[right - max_size]]

        return max_size

Time & Space Complexity

• Time complexity: $O(n)$
• Space complexity: $O(n)$

Where $n$ is the length of the input string s and $k$ is the maximum number of distinct characters.

---

Common Pitfalls

Not Removing Zero-Count Characters from the Map

When shrinking the window and decrementing character counts, failing to remove characters with zero count from the hash map leads to incorrect distinct character counts. Always delete or remove entries when their count reaches zero to maintain an accurate count of distinct characters in the current window.

Off-by-One Errors in Window Size Calculation

A frequent mistake is calculating the window size as right - left instead of right - left + 1. Since both left and right are inclusive indices, the correct window size includes both endpoints. This off-by-one error leads to returning a result that is one less than the actual answer.

Handling Edge Cases with k = 0

When k is zero, no characters are allowed in the substring, so the answer should be 0. Some solutions forget to handle this edge case, leading to incorrect results or infinite loops when the while condition never terminates because the window can never be valid.