Sliding Window — "At Most K" vs. "Exactly K" Distinct Elements ​

Common Interview Questions ​

1. Subarrays with K Different Integers (LC 992)

   • Problem: Given an array, return the number of subarrays with exactly K different integers.
   • Sliding Window Signal: This is the most complex pattern. "Subarray" points to sliding window, but "exactly K" is the tricky part. A direct approach is very difficult because the condition isn't monotonic.
   • The Trick: The key is to realize count(exactly K) = count(at_most K) - count(at_most K-1). This breaks the problem into two solvable subproblems.
   • Goal: You will implement a helper function that counts all subarrays with at most k distinct elements. You then call this helper twice, helper(K) and helper(K-1), and return the difference.

2. Longest Substring with At Most K Distinct Characters (LC 340)

   • Problem: Find the length of the longest substring containing at most K distinct characters.
   • Sliding Window Signal: This is a more standard problem. "Longest substring" and a property ("at most K distinct") point directly to a variable-size window.
   • Window State: A hash map is needed to track character frequencies. The shrink condition is len(map) > K.
   • Goal: This is a "longest window" problem and serves as the conceptual building block for the "exactly K" problems.

3. Count Number of Nice Subarrays (LC 1248)

   • Problem: A "nice" subarray has exactly k odd numbers. Find the total number of nice subarrays.
   • Sliding Window Signal: This is a variation where the property isn't about distinct elements, but a count of elements with a certain property (being odd). The "exactly K" structure suggests the at_most(K) - at_most(K-1) approach.
   • Window State: Instead of a hash map of distinct elements, you just need a single counter for the number of odd numbers in the current window.
   • Goal: Re-use the at_most helper logic. at_most(K) will count subarrays with K or fewer odd numbers. at_most(K-1) will count those with K-1 or fewer. The difference gives you those with exactly K.

A very common category of sliding window problems involves constraints on the number of unique elements within the window. Understanding how to handle "at most K" is the building block for solving the more complex "exactly K."

"At Most K" Distinct Elements ​

This is the standard version of the problem and fits the variable-size window pattern perfectly. The condition to maintain is len(window_counts) <= k.

When to Use:

• Keywords: "at most k distinct characters," "no more than k unique numbers."
• This is a "longest" window type of problem. You expand as much as possible, and only shrink when the number of distinct elements exceeds k.

Example Problem: Longest Substring with At Most K Distinct Characters (LC 340) ​

This is the canonical example. Find the length of the longest substring with no more than k distinct characters.

from collections import defaultdict

def longest_substring_at_most_k_distinct(s, k):
    if k == 0:
        return 0
        
    left = 0
    max_len = 0
    char_counts = defaultdict(int)
    
    for right in range(len(s)):
        # Expand window
        char_counts[s[right]] += 1
        
        # Shrink window if condition is violated
        while len(char_counts) > k:
            char_counts[s[left]] -= 1
            if char_counts[s[left]] == 0:
                del char_counts[s[left]]
            left += 1
            
        # Update answer with the current valid window size
        max_len = max(max_len, right - left + 1)
        
    return max_len

"Exactly K" Distinct Elements ​

This is a much trickier variation. You cannot use a single sliding window to directly find windows with exactly k distinct elements. The property len(window_counts) == k is not monotonic—shrinking a valid window might keep it valid, or it might invalidate it.

The Key Insight: The number of subarrays with exactly k distinct elements is equal to the number of subarrays with at most k distinct elements minus the number of subarrays with at most k-1 distinct elements.

count(exactly k) = count(at most k) - count(at most k - 1)

This transforms the problem from one complex sliding window into two simpler, standard ones.

Example Problem: Subarrays with K Different Integers (LC 992) ​

Given an array nums of positive integers, return the number of contiguous subarrays where the number of different integers is exactly k.

from collections import defaultdict

def subarrays_with_k_distinct(nums, k):
    """
    Calculates the number of subarrays with exactly k distinct elements.
    This is equivalent to:
      (number of subarrays with at most k distinct)
    - (number of subarrays with at most k-1 distinct)
    """
    return at_most_k_distinct(nums, k) - at_most_k_distinct(nums, k - 1)

def at_most_k_distinct(nums, k):
    """
    Helper function to count the number of subarrays with at most k distinct elements.
    For each `right`, the number of valid subarrays ending at `right` is `right - left + 1`.
    """
    if k < 0:
        return 0
        
    left = 0
    count = 0
    freq = defaultdict(int)
    
    for right in range(len(nums)):
        freq[nums[right]] += 1
        
        while len(freq) > k:
            freq[nums[left]] -= 1
            if freq[nums[left]] == 0:
                del freq[nums[left]]
            left += 1
            
        # The key step: for a valid window [left, right], any subarray
        # ending at `right` that starts at or after `left` is also valid.
        # There are (right - left + 1) such subarrays.
        count += (right - left + 1)
        
    return count

How the Algorithm Works ​

• At Most K: This is a standard "longest" window problem. The algorithm expands the window with the right pointer and uses a hash map to track distinct element frequencies. If len(hash_map) exceeds k, it shrinks the window from the left until the count of distinct elements is back down to k, ensuring the window is always valid.
• Exactly K: This algorithm relies on a clever mathematical trick. It recognizes that a direct sliding window is too complex. Instead, it solves the problem by inclusion-exclusion: it counts all subarrays with at most K distinct elements and subtracts all subarrays with at most K-1 elements, leaving only those with exactly K.

Tricky Parts & Decision Points ​

1. Recognizing the "Exactly K" Trick: The biggest hurdle is realizing that you can't solve "exactly K" directly. If you try, you'll find that your window shrinking logic becomes hopelessly complex. The key is to remember the at_most(K) - at_most(K-1) pattern.
2. The Counting Logic: In the at_most_k_distinct helper function, the line count += (right - left + 1) is non-obvious. It works because if the window [left, right] is valid (has at most K distinct elements), then any subarray ending at right that starts at or after left is also valid. This insight is crucial for counting problems.
3. Edge Cases: For at_most_k_distinct, remember to handle k=0 correctly. For subarrays_with_k_distinct, calling at_most_k_distinct(nums, k - 1) means you must handle the k=0 case inside the helper, as it will be called with -1.