Longest Substring with At Most K Distinct Characters

Direct Answer

Use a variable-size sliding window with a HashMap of character frequencies. Expand right and add characters; when the map has more than K distinct keys, shrink from the left, decrementing counts and removing a key when it hits zero. Track the maximum window length. This runs in O(n) time.

Deep Dive & Architecture

Use a variable-size window and a frequency map. Expand the right boundary for every character. When the map contains more than k distinct characters, move the left boundary forward, decreasing counts and removing a character when its count reaches zero.

Worked example: araaci, k = 2

The window grows through a, ar, ara, and araa; it contains only a and r, so its best length becomes 4. Adding c creates three distinct values. Remove characters from the left until only two remain: removing a twice does not remove it from the map, but removing r finally leaves a and c. The window is valid again. Adding i triggers another shrink.

The invariant is that the window is valid whenever its distinct count is at most k. Update the best length only after restoring that condition. Each character enters once and leaves at most once, so time is O(n), and the map uses O(k) space while valid.

For k = 0, the answer is normally 0. If the requirement says exactly k distinct characters rather than at most k, track the same windows but accept a candidate only when the map size equals k.

Code Example

import java.util.HashMap;
import java.util.Map;

public class LongestSubstringKDistinct {
    public static int lengthOfLongestSubstringKDistinct(String s, int k) {
        if (k == 0 || s.isEmpty()) return 0;
        Map<Character, Integer> freq = new HashMap<>();
        int left = 0, maxLength = 0;

        for (int right = 0; right < s.length(); right++) {
            char c = s.charAt(right);
            freq.put(c, freq.getOrDefault(c, 0) + 1);

            while (freq.size() > k) {                  // too many distinct -> shrink
                char l = s.charAt(left);
                freq.put(l, freq.get(l) - 1);
                if (freq.get(l) == 0) freq.remove(l);  // key removal keeps size correct
                left++;
            }
            maxLength = Math.max(maxLength, right - left + 1);
        }
        return maxLength;
    }

    public static void main(String[] args) {
        System.out.println(lengthOfLongestSubstringKDistinct("eceba", 2));  // 3 ("ece")
    }
}

Common Mistakes & Pitfalls

• Not removing zero-count keys: decrementing to zero but leaving the key makes map.size() overcount distinct characters — remove the key when it hits zero.
• Misreading map.size(): it's the number of keys (distinct characters), not the sum of frequencies.
• Shrinking too aggressively: the while condition is map.size() > k, not >= k, or you shrink valid windows.