Build a Sliding-Window Metrics ToolkitStep 3 of 5

Variable window: at most k distinct

12345

Step 3: Variable window: at most k distinct

A common analytics query is the longest span containing at most k distinct values, for example the longest period touching at most k unique endpoints. Use a variable window with a counts map. Expand on the right; while the map holds more than k distinct keys, shrink from the left, decrementing counts and deleting keys that reach zero.

Implement longest_at_most_k_distinct(s, k) returning the length of the longest substring with at most k distinct characters. If k <= 0, return 0.

Example: longest_at_most_k_distinct("eceba", 2) is 3, from "ece".

Hints
Starter code
def max_sum_window(nums, k):
    if k <= 0 or k > len(nums):
        return None
    window = sum(nums[:k])
    best = window
    for i in range(k, len(nums)):
        window += nums[i] - nums[i - k]
        if window > best:
            best = window
    return best


def longest_unique(s):
    last = {}
    start = 0
    best = 0
    for i, ch in enumerate(s):
        if ch in last and last[ch] >= start:
            start = last[ch] + 1
        last[ch] = i
        length = i - start + 1
        if length > best:
            best = length
    return best


def longest_at_most_k_distinct(s, k):
    # TODO: return the length of the longest substring with at most k distinct chars.
    # Use a counts map; while len(counts) > k, shrink from the left.
    # Return 0 when k <= 0.
    pass
Write it on a laptop

The editor and the test runner need a wide screen. Open this page on a desktop browser and your progress will be waiting.

PreviousNext step