// [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);
}
}