スライディングウィンドウ：「窓が何を保つか」を先に決める

スライディングウィンドウの難所は 2 ポインタではなく、窓が何を保つかにあります。そこが決まれば二重構造は自然にまとまり、決まらなければ同じ文字を何度も数え直す実装になります。

雛形：右を伸ばし、左を縮める

「重複のない最長部分文字列」を例にします。窓は [left, right] で、保つ状態は各文字が最後に現れた添字です。右端が 1 つ進むたび、その文字が窓の中に既にあれば、左端をその次の位置まで飛ばします。

function longestUnique(s) {
  const seen = new Map();
  let left = 0;
  let best = 0;
  for (let right = 0; right < s.length; right += 1) {
    const ch = s[right];
    const last = seen.get(ch);
    if (last !== undefined && last >= left) left = last + 1;
    seen.set(ch, right);
    best = Math.max(best, right - left + 1);
  }
  return best;
}

last >= left の判定が要点です。文字がもっと前に窓の外で現れている場合、今の窓とは無関係なので左端は動かしません。初心者がよく書くのは seen.has(ch) だけで止める実装です。

なぜ O(n) か

right も left も右にしか進まず、戻りません。right は n 歩、left も合計で高々 n 歩です。したがって二重に見えても総操作数は 2n 以下です。ただし左端を進めても縮小条件が逆転しないことが前提です。

使うべきでない場面

窓の妥当性が大きさに対して単調でない場合、つまり大きくすると妥当にも不正にもなり規則性がない場合、左端を進めても妥当性は戻らず 2 ポインタは成立しません。状態の設計を変えて不正を単調な量として表すか、累積和・単調キュー・二分探索に切り替えます。

同じ雛形の 3 変種

問題	保つ状態	縮める条件
重複のない最長部分文字列	各文字の最終添字	重複が現れた
最小被覆部分文字列	文字ごとの不足数	すべて覆った
固定長部分配列の最大和	窓の和	長さが k を超えた

最小被覆の問題では、答えの更新は伸ばすときではなく縮めるループの中で行います。最短の妥当な窓は縮めている最中のどこでも現れうるからです。

妥当性は単調であること。右端を伸ばすと妥当から不正へ（またはその逆へ）移り、左端を縮めれば元に戻せること。