§ Sliding window implementation style
I usually implement sliding window as:
int l = r = 0;
while (r < n) {
assert(l <= r);
if (extend_window) { r++; }
else {
l--;
}
}
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) {
int l = 0, r = 0;
int changed = 0;
while(r < n) {
assert(changed <= k);
assert(l <= r);
if (s[r] == c) { r++; }
else {
if (changed == k) {
if (s[l] != c) { changed--; }
l++;
} else {
r++;
changed++;
}
}
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;
int changed = 0;
for(int r = 0; r < n; ++r) {
if (s[r] != c) { changed++; }
while(changed > k && l < r) {
if (s[l] != c) { changed--; }
l++;
}
assert(l <= r);
best = max(best, r-l+1);
}
}