## § Sliding window implementation style

I usually implement sliding window as:
// [l, r)
int l = r = 0;
while (r < n) {
assert(l <= r);
if (extend_window) { r++; }
else {
l--; //contract window
}
}

However, there are cases where we have complicated invariants on the sliding window, such as a maximum length. An example is codeforces 676c , where we must maintain a sliding window which contains at most k >= 0 "illegal" elements. My flawed implementation using a while loop was:
int best = 0;
for(int c = 'a'; c <= 'b'; ++c) {
// window: [l, r)
int l = 0, r = 0;
// number of illegal letters changed. <= k
int changed = 0;
while(r < n) {
assert(changed <= k);
assert(l <= r);
if (s[r] == c) { r++; } // legal, extend.
else {
// need to change a letter to extend, s[r] != c.
if (changed == k) {
// cannot extend, contract from left.
if (s[l] != c) { changed--; }
l++;
} else {
// extend, spending a change.
r++;
changed++;
}
}
// keep track of best window size.
best = max(best, r-l);
}
}

Unfortunately, the above code is flawed. It does not work when the window size is zero. (TODO: explain) on the other hand, the implementation where we always stride forward with the r value in a for loop, and only deciding what happens with l does not suffer from this ( link to implementation ):
int best = 0;
for(int c = 'a'; c <= 'b'; ++c) {
int l = 0;
// number of illegal letters changed. <= k
int changed = 0;
// [l, r]
for(int r = 0; r < n; ++r) {
// change to 'a'.
if (s[r] != c) { changed++; }
// maintain invariants: must have changed <= k,
// and at the end of a loop trip, we must have l <= r.
while(changed > k && l < r) {
if (s[l] != c) { changed--; }
l++;
}
assert(l <= r);
// keep track of best window size.
best = max(best, r-l+1);
}
}