Sliding Window (Growing and Shrinking)

When the size isn't fixed

For the longest or shortest stretch that follows a rule, the window grows on the right and shrinks from the left whenever the rule is broken.

Longest stretch with no repeated letter

#include <algorithm>
#include <iostream>
#include <string>
using namespace std;

int longestUnique(const string& s) {
    int count[256] = {0};           // how many times each character is in the window
    int left = 0, best = 0;
    for (int right = 0; right < (int)s.size(); right++) {
        unsigned char c = s[right];
        count[c]++;
        while (count[c] > 1) {      // rule broken: shrink from the left
            count[(unsigned char)s[left]]--;
            left++;
        }
        best = max(best, right - left + 1);
    }
    return best;
}

int main() {
    cout << longestUnique("abcabcbb") << " " << longestUnique("bbbb") << " " << longestUnique("pwwkew") << endl;
    return 0;
}

Output

3 1 3

Each character enters and leaves the window at most once, so it's O(n) despite the inner while.

Shortest stretch with a big enough sum

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

int main() {
    vector<int> v = {2, 3, 1, 2, 4, 3};
    int target = 7;
    int left = 0, best = 0;
    long long total = 0;
    for (int right = 0; right < (int)v.size(); right++) {
        total += v[right];
        while (total >= target) {
            int len = right - left + 1;
            if (best == 0 || len < best) best = len;
            total -= v[left++];
        }
    }
    cout << best << endl;
    return 0;
}

Output

2

Common mistake: The shrinking trick needs positive numbers. With negatives, adding an item can make the total smaller and the logic breaks.