Have and need

The hardest window in the set: grow until the window is sufficient, then shrink while keeping it sufficient.

Here is that shape on a simpler requirement than the problem below: the shortest stretch containing at least k distinct characters.

1def shortest_with_k_distinct(text, k):2    counts = {}3    left = 04    best = len(text) + 15 6    for right in range(len(text)):7        counts[text[right]] = counts.get(text[right], 0) + 18 9        while len(counts) >= k:                    # still sufficient10            best = min(best, right - left + 1)11            leaving = text[left]12            counts[leaving] -= 113            if counts[leaving] == 0:14                del counts[leaving]15            left += 116 17    return best if best <= len(text) else 018 19print(shortest_with_k_distinct("abcba", 3))20print(shortest_with_k_distinct("aaa", 2))

Why it works

The two numbers

need is how many distinct characters must reach their required count. It is fixed once the target is read.

have is how many of those characters currently sit at or above their required count in the window. The window is sufficient exactly when have == need.

Update have only on the exact transition. When a character's window count rises to precisely its requirement, have goes up by one. When it falls to precisely one below, have goes down by one. Using a comparison such as greater-than-or-equal instead of exact equality double counts and quietly breaks everything.

1from collections import Counter2 3def has_all_required(window, required):4    """A slow but obviously correct sufficiency test, for comparison."""5    return all(window.get(ch, 0) >= count for ch, count in required.items())6 7required = Counter("aabc")8print(has_all_required(Counter("aab"), required))9print(has_all_required(Counter("aabbc"), required))

Before you start

Write down four things: what the window remembers, what makes it sufficient, where you record, and what you return when nothing works. If all four are on paper before you type, this problem is mechanical. If they are not, it is very hard.

Predict the output· 5 min

Predict the output: incrementing on the wrong condition

This counts how many characters have met their requirement, but uses the wrong condition. Type what it prints.

Python

1def have_count(window_counts, required):2    have = 03    for ch, count in window_counts.items():4        if ch in required and count >= required[ch]:5            have += 16    return have7 8def buggy_stream(text, required):9    counts = {}10    have = 011    for ch in text:12        counts[ch] = counts.get(ch, 0) + 113        if ch in required and counts[ch] >= required[ch]:14            have += 115    return have16 17print(have_count({"a": 4, "b": 1}, {"a": 2, "b": 1}))18print(buggy_stream("aaaab", {"a": 2, "b": 1}))

Printed output

Code lab· 22 min

Build the sufficiency tracker

Build the piece that the problem needs, on its own. make_requirement turns a string into a count map. update_have takes the window counts, the requirement, a character, and the direction it moved (+1 entering or -1 leaving), applies the change, and returns the delta that should be applied to have, which is 1, -1, or 0. is_sufficient reports whether every requirement is met.

solution.py

Tests

req = make_requirement("aabc")print(req)window = {}print(update_have(window, req, "a", 1), update_have(window, req, "a", 1))print(update_have(window, req, "b", 1), update_have(window, req, "a", 1))print(update_have(window, req, "a", -1))print(update_have(window, req, "a", -1))print(is_sufficient({"a": 2, "b": 1, "c": 1}, req), is_sufficient({"a": 1, "b": 1, "c": 1}, req))

Output

Run tests to see output.

Problem· 35 min

Minimum Window Substring

Read the constraints first and let them tell you what complexity is expected. Derive the approach, implement it, run the tests, and submit when it passes.

1def shortest_with_k_distinct(text, k):2 counts = {}3 left = 04 best = len(text) + 15 6 for right in range(len(text)):7 counts[text[right]] = counts.get(text[right], 0) + 18 9 while len(counts) >= k: # still sufficient10 best = min(best, right - left + 1)11 leaving = text[left]12 counts[leaving] -= 113 if counts[leaving] == 0:14 del counts[leaving]15 left += 116 17 return best if best <= len(text) else 018 19print(shortest_with_k_distinct("abcba", 3))20print(shortest_with_k_distinct("aaa", 2))

1from collections import Counter2 3def has_all_required(window, required):4 """A slow but obviously correct sufficiency test, for comparison."""5 return all(window.get(ch, 0) >= count for ch, count in required.items())6 7required = Counter("aabc")8print(has_all_required(Counter("aab"), required))9print(has_all_required(Counter("aabbc"), required))

1def have_count(window_counts, required):2 have = 03 for ch, count in window_counts.items():4 if ch in required and count >= required[ch]:5 have += 16 return have7 8def buggy_stream(text, required):9 counts = {}10 have = 011 for ch in text:12 counts[ch] = counts.get(ch, 0) + 113 if ch in required and counts[ch] >= required[ch]:14 have += 115 return have16 17print(have_count({"a": 4, "b": 1}, {"a": 2, "b": 1}))18print(buggy_stream("aaaab", {"a": 2, "b": 1}))

req = make_requirement("aabc")print(req)window = {}print(update_have(window, req, "a", 1), update_have(window, req, "a", 1))print(update_have(window, req, "b", 1), update_have(window, req, "a", 1))print(update_have(window, req, "a", -1))print(update_have(window, req, "a", -1))print(is_sufficient({"a": 2, "b": 1, "c": 1}, req), is_sufficient({"a": 1, "b": 1, "c": 1}, req))