Find longest substring with at most k distinct
Company: Snowflake
Role: Software Engineer
Category: Coding & Algorithms
Difficulty: medium
Interview Round: Onsite
Given a string s and an integer k, return the length of the longest contiguous substring that contains at most k distinct characters. Provide an O(n) sliding-window algorithm and analyze time and space complexity. Follow-up: modify your approach to also return the substring itself and to correctly handle Unicode grapheme clusters.
Quick Answer: This question evaluates a candidate's ability to design efficient string-processing algorithms using sliding-window techniques, reason about time and space complexity, and correctly handle Unicode grapheme clusters when returning substrings.
Given a string `s` and an integer `k`, return the length of the longest contiguous substring of `s` that contains at most `k` distinct characters.
Use an O(n) sliding-window approach: expand the window with the right pointer, track the count of each character in the window, and when the number of distinct characters exceeds `k`, shrink from the left until the constraint holds again. The answer is the maximum window size seen.
**Examples:**
- `s = "eceba", k = 2` → `3` (the substring `"ece"`)
- `s = "aa", k = 1` → `2` (the substring `"aa"`)
- `s = "abcabcabc", k = 2` → `2`
**Follow-up (discussion):** modify the approach to also return the substring itself, and discuss how to correctly handle Unicode grapheme clusters (iterate over graphemes rather than code units so multi-codepoint emoji/combining sequences count as one character).
Constraints
- 0 <= k <= length of s
- 0 <= length of s <= 10^5
- s consists of arbitrary characters (treat each code unit as one character for the core problem)
- If k <= 0, the answer is 0
Examples
Input: ("eceba", 2)
Expected Output: 3
Explanation: The longest substring with at most 2 distinct characters is "ece" (length 3).
Input: ("aa", 1)
Expected Output: 2
Explanation: With k=1, the whole string "aa" qualifies (one distinct character).
Hints
- Use two pointers (left and right) to define a sliding window, and a hash map to count occurrences of each character inside the window.
- Expand by moving `right` one step at a time. Whenever the count of distinct characters exceeds k, move `left` forward — decrementing counts — until the window again has at most k distinct characters.
- Track the best window length after each expansion. Because every character is added and removed at most once, the total work is O(n).