287. Longest Substring with At Most K Distinct Characters
You are given a string s of lowercase English letters and an integer k. Find the longest stretch of consecutive characters in s that uses no more than k different letters, and return its length.
Only the number of distinct letters is limited — each of them may repeat as often as it likes. If k is 0, no non-empty substring qualifies and the answer is 0.
Example 1:
Input: s = "eceba", k = 2
Output: 3
Explanation: "ece" uses only the letters e and c and has length 3. Any longer window would pull in a third letter.
Example 2:
Input: s = "aa", k = 1
Output: 2
Explanation: The whole string is a single distinct letter, so "aa" itself qualifies.
Constraints:
- 1 ≤ s.length ≤ 10⁵
- s consists of lowercase English letters only.
- 0 ≤ k ≤ 26
Hints:
A direct check of every substring is O(n²) or worse. Notice the structure instead: if a window of text has at most k distinct letters, so does every window inside it — shrinking never hurts, only growing does.
That monotonicity is the sliding-window signal. Keep a window [left, right] plus a count of each letter inside it. Move right forward one step at a time; whenever the window holds more than k distinct letters, advance left until one letter's count drops to zero and can be removed.
Track the number of distinct letters via the hash map's size (or a counter that changes only when a count moves to/from zero). Every index enters the window once and leaves at most once — that's the O(n) argument.
▶ Run checks these sample cases. Submit also runs hidden edge cases.
Input: s = "eceba", k = 2
Expected output: 3