Sliding Window

Window sum, average, maximum, frequency, and fixed-length substring problems.

Fixed-size windows

Window sum, average, maximum, frequency, and fixed-length substring problems.

Variable-size windows

Longest substring without repeating characters, minimum window substring, longest replacement window, smallest subarray with sum at least target (for positive values), and at-most/exactly k distinct elements.

Output (g++ 11.2, -std=c++17, warnings as errors, AddressSanitizer + UndefinedBehaviorSanitizer; Ubuntu 22.04 on WSL2):

“Exactly k” is computed as atMost(k) − atMost(k − 1), because “exactly” is not monotonic in the window size but “at most” is.

#include <bits/stdc++.h>
using namespace std;

int longestUnique(const string& s) {
    array<int, 256> last; last.fill(-1);
    int best = 0, left = 0;
    for (int right = 0; right < (int)s.size(); ++right) {
        unsigned char c = s[right];
        if (last[c] >= left) left = last[c] + 1;          // jump past the previous occurrence
        last[c] = right;
        best = max(best, right - left + 1);
    }
    return best;
}
string minWindow(const string& s, const string& t) {
    array<int, 256> need{};
    for (unsigned char c : t) ++need[c];
    int missing = (int)t.size(), bestL = 0, bestLen = INT_MAX, left = 0;
    for (int right = 0; right < (int)s.size(); ++right) {
        if (need[(unsigned char)s[right]]-- > 0) --missing;
        while (missing == 0) {                               // window valid: shrink from the left
            if (right - left + 1 < bestLen) { bestLen = right - left + 1; bestL = left; }
            if (++need[(unsigned char)s[left++]] > 0) ++missing;
        }
    }
    return bestLen == INT_MAX ? "" : s.substr(bestL, bestLen);
}
long long atMostK(const vector<int>& a, int k) {             // subarrays with at most k distinct values
    unorder
…

longest unique substring of "abcabcbb": 3
longest unique substring of "bbbbb": 1
longest unique substring of "pwwkew": 3
longest unique substring of "": 0
minimum window of "ADOBECODEBANC" containing "ABC": BANC
subarrays with exactly 2 distinct values: 7
smallest subarray with sum >= 7: length 2

Advanced topics

Monotonic deque, prefix-sum alternatives for negative numbers, streaming windows, and when the classic expand/shrink method fails because the validity predicate is not monotonic.

The shrink-from-the-left method needs this property: if a window is valid, every larger window containing it is valid too (or the reverse). With negative numbers, “sum ≥ target” loses that property — shrinking can increase the sum — so “smallest subarray with sum ≥ K” then needs prefix sums with a monotonic deque instead.

Quiz

? Why does `left = last[c] + 1` only happen when `last[c] >= left`?
+ An occurrence before the window is already irrelevant; moving left backwards would re-include duplicates. :: The window only moves forward.
- To save time. :: It is about correctness.
- Because characters are unique. :: They are not.
- It never matters. :: "abba" breaks without it.

? “Exactly k distinct” is computed as atMost(k) − atMost(k−1). Why not slide directly?
+ “Exactly k” is not monotonic — shrinking a valid window can make it invalid either way — but “at most k” is. :: The difference counts windows with exactly k.
- It is faster. :: Same complexity.
- To avoid a hash map. :: Both use one.
- It is a heuristic. :: It is exact.

? Which windows can use the simple expand/shrink method? (select all that apply)
+ Smallest subarray with sum ≥ target, all values positive :: Sum grows as the window grows.
+ Longest substring without repeats :: Validity is monotonic.
- Smallest subarray with sum ≥ target when values may be negative :: Needs prefix sums + monotonic deque.
+ At most k distinct values :: Monotonic.