Domain 2MediumCORE

Longest Substring with At Most K Distinct Characters

We are given a string s and an integer k. The goal is to find the length of the longest contiguous substring (window) that contains at most k distinct characters.

Domain: Medium•Updated: 2026-08-31
#Algorithms#LeetCode#qwen3.5:9b#Hash Table#Two Pointers#String#Sliding Window

340. Longest Substring with At Most K Distinct Characters

Model: qwen3.5:9b
Topics: Hash Table,Two Pointers,String,Sliding Window
FAANG asked: 1
Acceptance rate: 45.7%


Problem Breakdown

We are given a string s and an integer k. The goal is to find the length of the longest contiguous substring (window) that contains at most k distinct characters.

Inputs:

  • A string s consisting of lowercase English letters (implied by typical LeetCode context, though constraints allow general chars).
  • An integer k representing the maximum number of unique characters allowed in the window.

Outputs:

  • An integer representing the length of that substring. If no such non-empty substring exists (e.g., k=0k=0), return 0.

Constraints & Edge Cases:

  • String length up to 5×1045 \times 10^4. This rules out O(N2)O(N^2) solutions like checking every pair of indices and counting distincts naively.
  • k can be 0 or larger than the number of unique characters in s.
  • If k=0, any non-empty substring has at least one distinct character, so valid length is 0 unless string itself is empty (though constraint says 1≤s.length1 \le s.length).

Intuition

A brute-force approach would iterate through every possible start and end index of a substring (O(N2)O(N^2) pairs), calculate the number of unique characters for each window using a hash set, and track the maximum length. However, calculating distinct counts naively inside nested loops makes this O(N3)O(N^3) or at best O(N2)O(N^2). Given s.length is up to 50k, we need an O(N)O(N) solution.

The key insight here is that if a window [left, right] has more than k distinct characters, shrinking the window from the left will eventually reduce the number of unique characters back to at most k. Conversely, expanding the window to the right increases length but might violate the constraint. This monotonic property suggests a Sliding Window technique where we maintain two pointers (left, right) and adjust them dynamically while maintaining state (character counts) in constant time per step.

Approach

  1. Initialize two pointers, left at 0 and right starting from the beginning of the string.
  2. Use a hash map (dictionary) to store the frequency count of characters currently inside our window [left, right]. This allows us to track distinct counts in O(1)O(1) time.
  3. Iterate with right pointer across the entire string:
    • Add character at s[right] to our hash map (increment its count).
  4. Check if the number of keys in the hash map exceeds k.
  5. If it does, we must shrink the window from the left until the condition is satisfied again (len(map) <= k). To do this:
    • Decrement the count for character at s[left].
    • Remove the key entirely if its count drops to zero (this ensures our map size accurately reflects distinct characters).
    • Increment left pointer.
  6. At every valid state, update a global maximum length variable with (right - left + 1). Note: We can also just calculate max at the end or after each shrink; standard practice is to track it continuously.

Complexity Analysis

  • Time: O(N)O(N) where NN is s.length. Both pointers (left and right) traverse the string at most once from left to right. Dictionary operations (insert, delete) are amortized O(1)O(1).
  • Space: O(K)O(K) or O(Σ)O(\Sigma) depending on alphabet size Σ\Sigma, where we store counts for characters currently in our window. Since we enforce a constraint of k distinct characters, the map never grows larger than min(N, k) entries (effectively bounded by constant 50 given constraints).

Solution

from collections import defaultdict

class Solution:
    def lengthOfLongestSubstringKDistinct(self, s: str, k: int) -> int:
        # Edge case handling for k=0 or empty string logic naturally covered below
        
        char_count = defaultdict(int)
        left = 0
        max_len = 0
        
        for right in range(len(s)):
            c_right = s[right]
            
            # Add current character to window
            char_count[c_right] += 1
            
            # If distinct characters exceed k, shrink from the left
            while len(char_count) > k:
                c_left = s[left]
                
                # Decrement count for leaving character
                if char_count[c_left] == 0:
                    del char_count[c_left] 
                else:
                    char_count[c_left] -= 1
                
                left += 1
            
            # Update max length found so far
            current_len = right - left + 1
            if current_len > max_len:
                max_len = current_len
        
        return max_len

# Note for interview context: 
# The logic above handles k=0 correctly because len(char_count) will be >= 1 immediately,
# triggering the while loop until window is empty (left becomes right + 1), resulting in length 0.

Edge Cases Handled

  • k = 0: Any character added makes len(char_count) equal to 1. The while loop triggers immediately and shrinks the window until it’s empty, returning a max length of 0 (correct behavior).
  • All characters same with k=1: Window expands fully across string; map size stays at 1; returns total length NN.
  • k > distinct chars in s: The while loop never triggers. Map grows to full unique set, window covers entire string. Returns NN.
  • Empty input (if constraints allowed): Loop range is empty, returns initial max_len = 0.