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
sconsisting of lowercase English letters (implied by typical LeetCode context, though constraints allow general chars). - An integer
krepresenting 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., ), return 0.
Constraints & Edge Cases:
- String length up to . This rules out solutions like checking every pair of indices and counting distincts naively.
kcan be 0 or larger than the number of unique characters ins.- 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 ).
Intuition
A brute-force approach would iterate through every possible start and end index of a substring ( 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 or at best . Given s.length is up to 50k, we need an 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
- Initialize two pointers,
leftat 0 andrightstarting from the beginning of the string. - 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 time. - Iterate with
rightpointer across the entire string:- Add character at
s[right]to our hash map (increment its count).
- Add character at
- Check if the number of keys in the hash map exceeds
k. - 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
leftpointer.
- Decrement the count for character at
- 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: where is
s.length. Both pointers (leftandright) traverse the string at most once from left to right. Dictionary operations (insert, delete) are amortized . - Space: or depending on alphabet size , where we store counts for characters currently in our window. Since we enforce a constraint of
kdistinct characters, the map never grows larger thanmin(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. Thewhileloop 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 .
- k > distinct chars in s: The
whileloop never triggers. Map grows to full unique set, window covers entire string. Returns . - Empty input (if constraints allowed): Loop range is empty, returns initial
max_len = 0.