連続した区間（＝窓）を右へずらしながら、その区間についての答えを更新していく。
Two Pointers との違いは動く向き。two pointers は両端から中央へ寄るので区間は縮む一方だが、sliding window は左端も右端も右へ進む。右端を伸ばして窓を広げ、条件を外れたら左端を詰めて窓を縮める。どちらのポインタも戻らないので各要素は多くても2回しか触られない——だから O(n)。
窓幅が決まっている固定長（例: 連続 k 個の最大和）と、条件しだいで伸び縮みする可変長（例: 重複のない最長部分文字列）の2種類がある。
12. Best Time to Buy and Sell Stock
https://neetcode.io/problems/buy-and-sell-crypto/question?list=blind75
株価の配列から、1回だけ買ってそのあとの日に売るときの最大利益を返す。損しかしないなら取引しない（＝0）。
素直に書くと「買う日 × 売る日」の全ペアを試す二重ループで O(n²)。崩し方は 3（Two Sum）と同じで、片方を決めてしまう。
今日を売る日だと決めた瞬間、買値は考えるまでもなく今日より前でいちばん安かった値に決まる。他の日に買う理由がどこにもないから。つまり、覚えておくものは最安値ひとつだけでいい。
class Solution {
// 例: prices = [10, 1, 5, 6, 7, 1] -> 6
maxProfit(prices: number[]): number {
let minBuy = prices[0]; // ここまでで見た最安値 = 買う日
let maxProfit = 0; // 取引しない選択があるので初期値は 0
for (const sell of prices) {
// 今日を売る日とみなす。買値はもう決まっている
maxProfit = Math.max(maxProfit, sell - minBuy);
minBuy = Math.min(minBuy, sell);
}
return maxProfit;
}
}
時間 O(n)、空間 O(1)。添字 i を一度も使わないなら、ループは for...of に畳める。
どこが Sliding Window なのか
窓は [買った日 l, 今日 r] の区間。「この区間ぶん株を持ち続けている」という意味になる。
prices = 10 1 5 6 7 1
[--] r=0 窓は 10 だけ。利益 0
[--] r=1 1 < 10 -> 窓を捨てて 1 から作り直す（l が飛ぶ）
[-------] r=2 5 - 1 = 4
[------------] r=3 6 - 1 = 5
[-----------------] r=4 7 - 1 = 6 <- 最大
[----------------------] r=5 1 - 1 = 0（買値と同じなので l は動かない）
rは必ず1日ずつ右へ進む。ループそのものがrlは1つずつ動かない。より安い日が来たときだけそこへ飛ぶ
どちらも右へしか動かず戻らないので、配列を1周した時点で終わる。これが O(n) の中身。
コードの minBuy が、この l の位置の価格そのもの。答えに添字は要らないので、ポインタが変数1本に潰れている——l, r が見えないだけで、やっていることは窓の移動。
13. Longest Substring Without Repeating Characters
https://neetcode.io/problems/longest-substring-without-duplicates/question?list=blind75
同じ文字を含まない連続した部分文字列のうち、いちばん長いものの長さを返す。
12 は窓の「左端の価格」だけ覚えれば足りたが、今回は窓の中身そのものを覚える必要がある。「この文字はもう窓に入っているか」を O(1) で聞きたいので、入れ物は Set。
型は毎回これ。右端を1つ伸ばす → 条件を満たさなくなったら、満たすまで左端を詰める → 今の窓幅で答えを更新する。
class Solution {
// 例: s = "zxyzxyz" -> 3
// 0123456
lengthOfLongestSubstring(s: string): number {
// 窓 [l, r] の中にいる文字。窓の中身と常に一致させる
const window = new Set<string>();
let l = 0;
let longest = 0;
for (let r = 0; r < s.length; r++) {
// 右端の文字が窓の中にあるなら、その文字が窓から出るまで左端を詰める。
// 例: 窓が "zxy"（l=0, r=2）のとき、r=3 に 'z' が来る
// -> 窓に 'z' がいるので、左端の s[0]='z' を捨てて l=1
// -> 窓は "xy"。'z' がいなくなったので停止
while (window.has(s[r])) {
window.delete(s[l]);
l++;
}
window.add(s[r]); // 窓は "xyz"（l=1, r=3）になった
// 添字は両端とも含むので +1（幅ではなく個数を数えている）。3 - 1 + 1 = 3
longest = Math.max(longest, r - l + 1);
}
return longest;
}
}
l も r も右に進むだけなので、各文字は add で1回・delete で高々1回しか触られない。時間 O(n)、空間 O(m)（m は使われている文字の種類数）。
if ではなく while である理由
重複が見つかったとき、左端を1つ動かせば済むとは限らない。捨てるべきなのは「ぶつかった文字が窓から出るまで」なので、そこまで詰め続ける。
s = "abcbd"
01234
r=3 の 'b' が窓 [0,2]="abc" とぶつかる
l=0: 'a' を捨てる -> 窓は "bc"。まだ 'b' がいる
l=1: 'b' を捨てる -> 窓は "c"。ぶつからなくなったので停止
'b' を入れて 窓 [2,3]="cb"
r=4 の 'd' はぶつからない -> 窓 [2,4]="cbd" -> 3
l++ を1回で済ませると、l が 1 のまま 'b' を入れることになり、窓が "bcb" という重複を含んだ状態になる。そのまま 'd' まで伸びて 4 を返してしまう（正解は 3）。窓の中身と Set の中身がズレた時点で、以降の判定は全部信用できない。
長さを変数で持たない
length のようなカウンタを別に持って l++ のたびに調整する書き方もできるが、幅は r - l + 1 でいつでも計算できるので持たないほうがいい。同じ事実を2箇所で管理すると、片方の更新漏れがそのままバグになる。状態は l と Set の2つだけに絞れば、壊れる余地がなくなる。
応用: 「連続した区間で、条件を満たす最長」と来たら sliding window の可変長。書くことは3つだけ——右端を伸ばす / 条件を壊したら左端を詰める / 窓幅で答えを更新する。変わるのは「条件」と「窓の状態をどう持つか（Set か Map か カウンタか）」だけ。
14. Longest Repeating Character Replacement
https://neetcode.io/problems/longest-repeating-substring-with-replacement/question?list=blind75
大文字だけの文字列 s について、好きな文字を k 個まで別の文字に置き換えてよい。そのうえで「全部同じ文字」にできる連続部分文字列の、最長の長さを返す。
詰まるのは「どう置き換えるか」を考えるから
"AAABABB", k = 1 を前にして「どの文字を何に替えるか」を考え始めると、選択肢が爆発して手が止まる。この問題は文字列を1文字も書き換えない。置換は最後まで想像の中だけで、コードに出てくるのは数え上げだけ。
考える順番はこう。
① まず窓を1つ固定して、「この窓は作れるか？」だけを考える。
窓 "AAAB" を全部同じ文字にしたい。残す文字は何にすべきか——その窓でいちばん多い文字一択。A を残せば置換は B の1個で済むが、B を残すと A 3個ぶんかかる。多いほうを残すのが常に得。
② すると、必要な置換数が引き算1回で出る。
必要な置換数 = 窓の長さ − 窓の中でいちばん多い文字の個数
"AAAB" なら 4 − 3（A が3個）= 1
この窓が作れる ⟺ 必要な置換数 <= k
「置き換える」という操作が、「窓の中の文字を数える」に化けた。 ここが本問の全部。
③ 判定式ができれば、あとは 13 と同じ型に乗るだけ。
「連続した区間で、条件を満たす最長」なので sliding window の可変長。右端を伸ばし、置換数が k を超えたら左端を詰め、窓幅で答えを更新する。
const A = 'A'.charCodeAt(0);
class Solution {
// 例: s = "AAABABB", k = 1 -> 5（"AAABA" の B を A に替える）
characterReplacement(s: string, k: number): number {
// 「窓の中に」各文字が何個あるか。大文字のみなので26個の配列で足りる（2 と同じ手）
// count[0] が 'A' の個数、count[1] が 'B' の個数……
const count = new Array(26).fill(0);
let l = 0;
let longest = 0;
for (let r = 0; r < s.length; r++) {
count[s.charCodeAt(r) - A]++; // 右端の文字を窓に入れる
// 必要な置換数が k を超えているあいだ、左端を詰める。
// 例: 窓 "AAABAB"（A が4個）は 6 - 4 = 2 個の置換が要る。k = 1 なら大きすぎるので縮める
while (r - l + 1 - Math.max(...count) > k) {
count[s.charCodeAt(l) - A]--; // 左端の文字を窓から出す
l++;
}
// ここに来た時点で、窓は必ず「k 回以内で全部同じにできる」状態
longest = Math.max(longest, r - l + 1);
}
return longest;
}
}
Math.max(...count) が「いちばん多い文字の個数」。中は常に26要素なので、この1行は定数時間とみなせる。全体で時間 O(26n) = O(n)、空間 O(26) = O(1)。
s = "AAABABB", k = 1 を追ってみる
s = A A A B A B B
0 1 2 3 4 5 6
r=0 [A] 窓長1 最多A=1 置換 0 -> longest 1
r=1 [AA] 窓長2 最多A=2 置換 0 -> longest 2
r=2 [AAA] 窓長3 最多A=3 置換 0 -> longest 3
r=3 [AAAB] 窓長4 最多A=3 置換 1 <= k -> longest 4
r=4 [AAABA] 窓長5 最多A=4 置換 1 <= k -> longest 5 <- 最大
r=5 [AAABAB] 窓長6 最多A=4 置換 2 > k -> 縮める
[AABAB] 窓長5 最多A=3 置換 2 > k -> まだ縮める
[ABAB] 窓長4 最多A=2 置換 2 > k -> まだ縮める
[BAB] 窓長3 最多B=2 置換 1 <= k -> 停止。longest は 5 のまま
r=6 [BABB] 窓長4 最多B=3 置換 1 <= k -> longest は 5 のまま
-> 5
r=4 の窓 "AAABA" は「B を1個 A に替えれば AAAAA」なので条件を満たす。実際に替えてはいない。「4 個の A と、それ以外1個」という数え上げだけで判断している。
応用: 「〜を k 個まで変更してよい。条件を満たす最長は？」は sliding window の定番の形。やることは**「今の窓を条件に合わせるコストを、数え上げで表す」**の1点だけ。コストが k 以下なら伸ばし、超えたら縮める。この問題ではそれが 窓の長さ − 最頻文字の個数 だった。