Step 6 of 6

Challenge: sliding window

A sliding window keeps a range [left, right] of the data that only ever moves forward. Each element enters the window once and leaves once, so the whole scan is O(n), even though it effectively examines a huge number of ranges.

Here's a window that grows and shrinks: the shortest stretch of days whose rainfall reaches a target.

#include <iostream>
#include <vector>

int shortest_reaching(const std::vector<int>& v, int target) {
    int best = 0, sum = 0, left = 0;
    for (int right = 0; right < (int)v.size(); right++) {
        sum += v[right];                        // grow: v[right] enters
        while (sum >= target) {                 // shrink while still valid
            int len = right - left + 1;
            if (best == 0 || len < best) best = len;
            sum -= v[left];                     // v[left] leaves
            left++;
        }
    }
    return best;                                // 0 means never reached
}

int main() {
    std::vector<int> rain = {2, 1, 5, 1, 3, 2, 8};
    std::cout << shortest_reaching(rain, 8) << "\n";    // just the 8 at the end
    std::cout << shortest_reaching(rain, 9) << "\n";    // 5 1 3, or 2 8
    std::cout << shortest_reaching(rain, 100) << "\n";
}

1
2
0

The pattern

1. Move right forward one step, adding the new element to the window's state.
2. While the window breaks (or satisfies) the condition, move left forward, removing elements from the state.
3. Record the answer at the right moment.

left never moves backwards, and right goes through the data once, so the total work is O(n).

Your task: longest substring with no repeats

The window's state is "the last position where each character was seen", kept in an array of 256 ints set to -1. When s[right] was last seen inside the window (at a position >= left), jump left to one past that position. Then record s[right]'s new position and update the best length right - left + 1. Index the array with (unsigned char)s[right] so characters above 127 don't give a negative index.

Your turn: write int longest_unique(const std::string& s): the length of the longest substring with no repeated characters. For "abcabcbb" it's 3 ("abc").

Idea: move right forward one character at a time. If that character already appears inside the window, jump left past its previous position. Remember each character's last position in an array of 256 ints.

Previous: Prefix sums