Problem: Longest Substring with K Distinct Characters

Problem Statement

Given a string, find the length of the longest substring in it with no more than k distinct characters.

Approach: Variable-Size Sliding Window

1. Initialize: windowStart = 0, maxLength = 0, and a HashMap to store character frequencies.
2. Expand: Move windowEnd forward, adding characters to the map.
3. Shrink: If the map size exceeds k, remove characters from the windowStart until the map size is k or less.
4. Update: Record the maximum window length seen so far.

Java Implementation

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

public int findLongestSubstringWithKDistinct(String str, int k) {
    if (str == null || str.length() == 0 || k == 0) return 0;

    int windowStart = 0, maxLength = 0;
    Map<Character, Integer> charFrequencyMap = new HashMap<>();

    for (int windowEnd = 0; windowEnd < str.length(); windowEnd++) {
        char rightChar = str.charAt(windowEnd);
        charFrequencyMap.put(rightChar, charFrequencyMap.getOrDefault(rightChar, 0) + 1);

        // Shrink the window until we have 'k' distinct characters
        while (charFrequencyMap.size() > k) {
            char leftChar = str.charAt(windowStart);
            charFrequencyMap.put(leftChar, charFrequencyMap.get(leftChar) - 1);
            if (charFrequencyMap.get(leftChar) == 0) {
                charFrequencyMap.remove(leftChar);
            }
            windowStart++;
        }
        maxLength = Math.max(maxLength, windowEnd - windowStart + 1);
    }
    return maxLength;
}

Complexity Discussion

• Time Complexity: $O(n)$. Each character is processed at most twice (once by windowEnd and once by windowStart).
• Space Complexity: $O(k)$ for the frequency map.