Google — Longest Substring with K Distinct Characters (Sliding Window)

Problem Statement#

Given a string s and an integer k, return the length of the longest substring that contains at most k distinct characters.

Constraints:

• 1 <= s.length <= 5 * 10^4
• 0 <= k <= 50
• s consists of English letters

Input:  s = "eceba", k = 2
Output: 3  (substring "ece")

Input:  s = "aa", k = 1
Output: 2  (substring "aa")

Why This Problem Matters#

Longest Substring with K Distinct Characters (LeetCode 340) is a Google interview classic that appears in both phone screens and onsite rounds. Google uses this to test the sliding window pattern — one of the most powerful tools for substring/subarray optimization problems. Engineers who can apply sliding window efficiently handle a huge class of problems that appear in search indexing, text processing, and stream analytics.

The brute force generates all O(N^2) substrings and checks each — O(N^3) total. The sliding window solves this in O(N) by maintaining a frequency map of characters in the current window. When the window has more than k distinct characters, shrink from the left until the constraint is satisfied again.

Amazon and Microsoft ask identical variants: longest substring with at most 2 distinct characters (LeetCode 159), or the fruit basket problem (LeetCode 904) which is isomorphic. Understanding this template unlocks all of them.

The Core Insight#

Use two pointers left and right. Expand right by adding s[right] to a frequency map. When the map has more than k keys, shrink from left: decrement freq[s[left]], remove the key if count drops to zero, then advance left. At every step where the window is valid (at most k distinct), update the maximum length.

The window always contains a contiguous substring. The frequency map tracks distinct character counts. The "shrink until valid" operation is the key — and because each character is added and removed at most once, total work is O(N).

Visual Dry Run#

s = "eceba", k = 2

Solution (Optimal)#

from collections import defaultdict
 
class Solution:
    def lengthOfLongestSubstringKDistinct(self, s: str, k: int) -> int:
        if k == 0:
            return 0
 
        freq = defaultdict(int)
        left = 0
        max_len = 0
 
        for right in range(len(s)):
            freq[s[right]] += 1
 
            while len(freq) > k:
                freq[s[left]] -= 1
                if freq[s[left]] == 0:
                    del freq[s[left]]
                left += 1
 
            max_len = max(max_len, right - left + 1)
 
        return max_len

var lengthOfLongestSubstringKDistinct = function(s, k) {
    if (k === 0) return 0;
 
    const freq = new Map();
    let left = 0;
    let maxLen = 0;
 
    for (let right = 0; right < s.length; right++) {
        freq.set(s[right], (freq.get(s[right]) || 0) + 1);
 
        while (freq.size > k) {
            const c = s[left];
            freq.set(c, freq.get(c) - 1);
            if (freq.get(c) === 0) freq.delete(c);
            left++;
        }
 
        maxLen = Math.max(maxLen, right - left + 1);
    }
 
    return maxLen;
};

Time: O(N) — each character is added and removed from the frequency map at most once Space: O(k) — the frequency map holds at most k+1 keys before shrinking

Common Mistakes#

• Deleting the key from the map before checking the count — misses the "still in window" case
• Returning right - left instead of right - left + 1 — off-by-one in window length
• Not handling k = 0 edge case — should return 0 immediately
• Using a set (only membership) instead of a frequency map — cannot shrink correctly when characters repeat
• Shrinking only once per expansion instead of using a while loop — window may still be invalid

Interview Tips#

• State the sliding window invariant clearly: the window always has at most k distinct characters
• When expanding violates the constraint, shrink with a while loop, not an if statement
• Mention that the frequency map deletion step is critical — only delete when count hits 0
• This is isomorphic to the "fruit basket" (LeetCode 904) and "at most 2 distinct" (LeetCode 159) problems
• The same template handles "at most k" and "exactly k" (exactly k = atMost(k) - atMost(k-1))

Follow-up Questions#

• How do you find the longest substring with exactly k distinct characters? — atMost(k) - atMost(k-1)
• What if the string is a stream of characters? — Sliding window works; no need to store full string
• What if k is very large (larger than the alphabet)? — Answer is always the full string length
• How would you return the actual substring, not just the length? — Track left pointer at each max update
• What is the longest substring with all distinct characters? — k = number of unique chars; or use the classic sliding window set

Key Takeaways#

• The sliding window with a frequency map solves this in O(N) time and O(k) space
• Expand right freely; shrink left only when the number of distinct keys exceeds k
• Delete a key from the frequency map only when its count drops to 0 — not before
• The window length is right - left + 1 at each valid state
• Google uses this to screen sliding window fluency — a pattern that unlocks dozens of substring problems
• The "at most k distinct" template directly generalizes to "exactly k distinct" with a subtraction trick
• LeetCode 340 (premium) has identical twins: LeetCode 159 (k=2) and LeetCode 904 (fruit basket)