Sliding window

The pattern

A window is a contiguous stretch [left, right] of the array or string. You extend it on the right, and when it becomes invalid you shrink it from the left. You never move left backwards.

The insight: moving the window by one position changes only two elements - one enters, one leaves. So the answer for the new window can be computed from the old one in O(1) instead of rescanning it in O(k).

Recognise it from: contiguous, subarray, substring, consecutive, longest/shortest ... such that.

Warm-up: fixed size window

Maximum sum of any k consecutive elements.

Brute force recomputes each window: O(n x k).

#include <iostream>
#include <vector>
#include <unordered_map>
#include <algorithm>
using namespace std;

int max_sum_k(const vector<int> &a, int k) {
    int n = a.size();
    if (n < k) return 0;

    int window = 0;
    for (int i = 0; i < k; i++) window += a[i];

    int best = window;
    for (int i = k; i < n; i++) {
        window += a[i] - a[i - k];      // add the new, remove the old
        best = max(best, window);
    }
    return best;
}

int main() {
    vector<int> a = {2, 1, 5, 1, 3, 2};
    cout << max_sum_k(a, 3) << "\n";     // 9  (5 + 1 + 3)
    return 0;
}

The single line window += a[i] - a[i-k] is the whole pattern. O(n) time, O(1) space.

The real problem: variable size window

Find the length of the longest substring with no repeating characters.

"abcabcbb" -> 3, from "abc" "bbbbb" -> 1 "pwwkew" -> 3, from "wke"

Step 1: brute force

Check every substring for duplicates: O(n^3), or O(n^2) with a set per start position. For a 100,000-character string that is far too slow.

Step 2: think in windows

Keep a window that contains no repeats. Extend right one character at a time. When the new character is already inside the window, the window is invalid - so move left forward until it is valid again.

Trace "pwwkew":

Answer 3.

Step 3: the code

The trick is storing the last index of each character, so left can jump straight there instead of stepping one at a time.

int longest_unique(const string &s) {
    unordered_map<char, int> last_seen;   // char -> last index it appeared
    int left = 0;
    int best = 0;

    for (int right = 0; right < (int)s.size(); right++) {
        char c = s[right];
        if (last_seen.count(c) && last_seen[c] >= left) {
            left = last_seen[c] + 1;      // jump past the earlier copy
        }
        last_seen[c] = right;
        best = max(best, right - left + 1);
    }
    return best;
}

int main() {
    cout << longest_unique("abcabcbb") << "\n";   // 3
    cout << longest_unique("bbbbb") << "\n";      // 1
    cout << longest_unique("pwwkew") << "\n";     // 3
    cout << longest_unique("") << "\n";           // 0
    return 0;
}

O(n) time - right moves n times, left only ever moves forward. O(min(n, alphabet)) space.

Trace "abba" to see it. At right = 3 the character is 'a', last seen at index 0. But left is already 2. Without the check, left would be set back to 1, re-admitting 'b' and reporting a window of length 3 containing two b's.

The third shape: shrink to the minimum

Smallest subarray whose sum is at least S.

int min_subarray_len(const vector<int> &a, int S) {
    int n = a.size();
    int left = 0, sum = 0, best = n + 1;

    for (int right = 0; right < n; right++) {
        sum += a[right];
        while (sum >= S) {                    // valid - try to shrink
            best = min(best, right - left + 1);
            sum -= a[left];
            left++;
        }
    }
    return best == n + 1 ? 0 : best;
}

int main() {
    vector<int> a = {2, 3, 1, 2, 4, 3};
    cout << min_subarray_len(a, 7) << "\n";   // 2  ({4, 3})
    return 0;
}

The while looks like it makes this O(n^2). It does not: left increases at most n times across the entire run, so the total work is O(n). Being able to explain that is worth as much as the code.

Practice, in this order

1. Longest substring with at most k distinct characters.
2. Permutation in string - fixed window plus a frequency count.
3. Maximum of every window of size k, using a deque.
4. Minimum window substring - the hardest common one, and it is this exact

shrink pattern with a character count.