Longest Substring with At Most K Distinct Characters
Medium · Sliding Window · Hash Table · String · Sliding Window
Problem
Given a string s and an integer k, return the length of the longest substring of s that contains at most k distinct characters.
A substring is a contiguous run of characters. Uppercase and lowercase letters count as different characters. If k is 0, no non-empty substring qualifies and the answer is 0.
Examples
Input: s = "abaccc", k = 2 Output: 4
"accc" uses only a and c and is longer than "aba".
Input: s = "aa", k = 0 Output: 0
No character may be used, so only the empty substring qualifies.
Input: s = "eceba", k = 2 Output: 3
"ece" uses e and c. Adding b on the right would make three letters.
Constraints
- 1 <= len(s) <= 5 · 10^4
- 0 <= k <= 50
- s consists of English letters
Approaches
- Every start, extend until too many characters — time O(n²), space O(min(n, k))
Follow-up
What if the characters arrive as a stream and you can only keep O(k) memory? Keep, for each character in the window, the index of its last occurrence (an ordered map from character to last index). When a (k + 1)-th character arrives, the new window starts just after the smallest last index, which you can evict without remembering the text itself.
Related problems
Start free on Cariara · Coding problems · System design studio
