Longest Substring with at most K Distinct Characters

This is a classic dynamic sliding window problem. We expand the window by moving right forward and maintain a HashMap that counts the frequency of each character in the current window. When the number of distinct characters exceeds k, we shrink the window from the left until we are back to at most k distinct characters.

Implementation steps:

• Use a HashMap<Character, Integer> to track the frequency of each character in the window.
• Expand the window by adding s.charAt(right) to the map.
• When map.size() > k, shrink the window from the left: decrement the count of s.charAt(left) and remove it from the map when its count reaches 0.
• After shrinking, update maxLen with the current window size.

public int lengthOfLongestSubstringKDistinct(String s, int k) {
    if (k == 0 || s == null || s.isEmpty()) return 0;

    Map<Character, Integer> freq = new HashMap<>(); // char -> frequency in window
    int left = 0, maxLen = 0;

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

        // Shrink window until we have at most k distinct characters
        while (freq.size() > k) {
            char leftChar = s.charAt(left);
            freq.put(leftChar, freq.get(leftChar) - 1);
            if (freq.get(leftChar) == 0) {
                freq.remove(leftChar); // distinct count drops by 1
            }
            left++;
        }

        maxLen = Math.max(maxLen, right - left + 1);
    }
    return maxLen;
}

Trace through Example 1: s = "eceba", k = 2

• Time complexity: O(n). Each character is added to the window once by right and removed at most once by left. Total operations: O(2n) = O(n).
• Space complexity: O(k). The frequency map holds at most k + 1 entries at any point (before shrinking).