Sliding Window — Longest Substring with At Most K Distinct Characters
↗ LeetCode: Longest Substring with At Most K Distinct Characters · Medium · pattern chapter →
Given a string s and integer k, return the length of the longest substring containing at most k distinct characters.
Example 1 — s = "eceba", k = 2 → 3 (window "ece") Example 2 — s = "aa", k = 1 → 2Example 3 — s = "a", k = 0 → 0
Constraints — 1 ≤ n ≤ 5 · 10⁴; 0 ≤ k ≤ 50. Brute expands every window in O(n²·k) = 10¹⁰·k ops at n=10⁵ (TLE). Sliding window with a freq map is O(n) = 10⁵ ops.
Interview timer00:00
Approach 1 — Try every substring
Intuition. For each s[i..j], count distinct characters; track the longest window with ≤ k distinct.
int lengthOfLongestSubstringKDistinctBrute(String s, int k) {
int n = s.length(), best = 0;
for (int i = 0; i < n; i++) {
Set<Character> distinct = new HashSet<>();
for (int j = i; j < n; j++) {
distinct.add(s.charAt(j));
if (distinct.size() <= k) best = Math.max(best, j - i + 1);
else break;
}
}
return best;
}Complexity — Time O(n²); Space O(σ).
Approach 2 — Sliding window with distinct counter
Insight from brute. Growing right never decreases distinct. Once distinct > k, we shrink left — decrementing each char's count; if a count hits 0, distinct drops.
int lengthOfLongestSubstringKDistinct(String s, int k) {
if (k == 0) return 0;
int[] cnt = new int[128];
int left = 0, distinct = 0, best = 0;
for (int right = 0; right < s.length(); right++) {
if (cnt[s.charAt(right)]++ == 0) distinct++;
while (distinct > k)
if (--cnt[s.charAt(left++)] == 0) distinct--;
best = Math.max(best, right - left + 1);
}
return best;
}Complexity — Time O(n) — each char enters and leaves once; Space O(σ) (≤ 128).
Approach 3 — Ordered map for k large (interview polish)
Insight from sliding. If k is very large (10⁴+), tracking distinct explicitly is still O(n), but managing a LinkedHashMap of last-seen indices can express the same logic in a tighter algorithm — remove the least-recently-used char and advance left past it in O(1).
int lengthOfLongestSubstringKDistinctLRU(String s, int k) {
LinkedHashMap<Character, Integer> lastIdx = new LinkedHashMap<>(k, 0.75f, false);
int left = 0, best = 0;
for (int right = 0; right < s.length(); right++) {
char c = s.charAt(right);
lastIdx.remove(c);
lastIdx.put(c, right);
if (lastIdx.size() > k) {
Map.Entry<Character, Integer> oldest = lastIdx.entrySet().iterator().next();
left = oldest.getValue() + 1;
lastIdx.remove(oldest.getKey());
}
best = Math.max(best, right - left + 1);
}
return best;
}Complexity — Time O(n); Space O(k).
Try it yourself
Complexity summary
| Approach | Time | Space | Interview grade |
|---|---|---|---|
| Every substring | O(n²) | O(σ) | baseline |
| Sliding window | O(n) | O(σ) | expected optimum |
| LRU-style ordered map | O(n) | O(k) | polish |
When to use which
- k = 2 → this is exactly Fruit Into Baskets.
- k = ∞ → this is Longest Substring Without Repeating Characters (k is unconstrained).
- k = size(alphabet) → answer is trivially
n. - Return the substring → track
(bestL, bestLen)and slice.
Related problems
- Longest Substring Without Repeating Characters — k = ∞
- Fruit Into Baskets — k = 2
- Subarrays with K Different Integers — count, not length
- Longest Substring with At Most Two Distinct Characters