スライディングウィンドウとは、leftからrightまでのリストの範囲で、動かしながらその要約を保ち続けるものです:累計、失敗の回数、各文字が最後に現れた位置などです。端を動かすとその要約が定数時間で更新されるので、同じ要素を二度足すことはありません。
k個の要素からなる固定ウィンドウでは、入る要素を足し、出る要素を引きます。可変ウィンドウは右端を1要素ずつ広げ、ルールに違反している間(文字の重複、失敗が多すぎるなど)、または目標をまだ満たしている間(合計に達する最短の区間など)は左から縮めます。
両端は前にしか進まないので、各要素は1回入って1回出ます:時間はO(n)で、追加の空間は合計ならO(1)、マップならO(k)です。縮める処理には、ウィンドウが広がるにつれて要約が一方向にだけ変化することが必要です。負の値があると、「合計が十分大きい間は縮める」が成り立たなくなります。空のリスト、リストと同じ長さのウィンドウ、すべて負の値、最後の要素で終わるウィンドウをテストしてください。