Sliding Window パターン
tsh1. Sliding Window パターンの基本アイデア
スライディングウィンドウアルゴリズムは、配列や文字列などのデータの連続する一部分（部分配列・部分文字列）を「ウィンドウ」として保持し、そのウィンドウをスライドさせながら処理を行う手法です。典型的には開始位置と終了位置を示す2つのポインタ（インデックス）を管理し、これらで定義されるウィンドウを順次右方向へ移動させていきます。一度に連続する要素をまとめて扱い、ウィンドウをずらしながら計算することで、全ての部分配列を一から計算するよりも効率的に結果を得ることができます。
特に問題の制約に応じてウィンドウサイズを動的に調整できる点が重要です。ウィンドウ内の要素が現在の問題の条件（制約）を満たしていれば右端を拡張してさらに要素を取り込み、条件を超えて不適合になった場合は左端を縮める、といった操作を繰り返すことで、連続するデータ範囲に対する問題を効率よく解くことができます。
tsh2. どのような問題に適用できるか
スライディングウィンドウパターンは、連続する部分配列や部分文字列を扱う多くの問題で有効です。配列や文字列中の要素が連続している範囲に対して探索・最適化を行う際、次のような例に適用できます。
-
固定長ウィンドウ
ウィンドウサイズがあらかじめ決まっている場合に有用です。たとえば、配列内で「長さ K の連続部分配列の合計が最大となる区間」を探索する問題などが挙げられます。 -
可変長ウィンドウ
問題の制約によってウィンドウサイズが動的に変化する場合に有用です。たとえば、文字列において「異なる文字が K 個以内」という制約を満たす最長部分文字列を求める問題や、「配列内で特定の合計以上になる最短の部分配列」を探索する問題などが代表的な例です。
いずれの場合でも、「連続する範囲」というキーワードが出てきたら、まずスライディングウィンドウのアプローチを検討してみるとよいでしょう。
tsh3. Python のサンプルコード
例題1: 固定長ウィンドウ（最大の連続部分和）
問題: 与えられた配列から、長さ K の連続部分配列の中で最大の合計値を求めます（典型的には「スライディングウィンドウを用いた部分配列の最大和」問題）。
以下の実装例では、まず先頭から長さ K のウィンドウの合計値を求め、その後はウィンドウを1つ右にスライドさせるたびに、出ていく要素を差し引き、新しく加わる要素を足して、合計を効率的に更新します。すべてのウィンドウの合計を確認し、最大値を求めることで、長さ K の部分配列の最大和を導きます。
def max_subarray_sum(arr, k):
# 配列arrの長さがK未満の場合、部分配列を作れないので None を返す
if k > len(arr):
return None
# 最初のウィンドウ（先頭からK要素）の合計を計算
current_sum = sum(arr[:k])
max_sum = current_sum
# ウィンドウを1つずつ右にスライドしながら合計を更新
for i in range(k, len(arr)):
# ウィンドウに新しい要素arr[i]を加え、ウィンドウから外れる古い要素arr[i-k]を差し引く
current_sum += arr[i] - arr[i - k]
# 合計がこれまでの最大値を上回ったら更新
if current_sum > max_sum:
max_sum = current_sum
# 計算された最大の連続部分和を返す
return max_sum
# 使用例:
print(max_subarray_sum([1, 4, 2, 10, 23, 3, 1, 0, 20], 4)) # 出力: 39 （23+3+1+12 の和）
例題2: 可変長ウィンドウ（異なる文字を K 個以内含む最長部分文字列）
問題: 与えられた文字列から、含まれる異なる文字が K 個以内であるような最長の部分文字列を求めます（文字種の種類数が K を超えない最長の連続文字列を求める問題）。
右端を進めながら文字を取り込み、ウィンドウ内の異なる文字数が K を超えた場合に左端を進めて条件を再度満たすよう調整することで、常に「異なる文字数が K 個以内」という条件を満たす範囲を探します。範囲のサイズを随時チェックし、最長となる区間を求めるアプローチです。
def longest_substring_at_most_k_distinct(s, k):
# 異なる文字を許容する数Kが0の場合、結果は空文字列
if k == 0:
return ""
n = len(s)
char_count = {} # ウィンドウ内の各文字の出現回数を記録する辞書
left = 0 # ウィンドウの左端インデックス
max_length = 0 # 発見した最長部分文字列の長さ
longest_substr = "" # 発見した最長部分文字列そのもの
# 右端のインデックスrightを動かしながらウィンドウを拡大
for right in range(n):
char = s[right]
# 文字charをウィンドウに追加（カウントを更新）
char_count[char] = char_count.get(char, 0) + 1
# ウィンドウ内の異なる文字数がKを超えている間、左端を動かして調整
while len(char_count) > k:
left_char = s[left]
# 左端の文字をウィンドウから除去（カウント減少）
char_count[left_char] -= 1
if char_count[left_char] == 0:
# 出現回数が0になった文字は辞書から削除（異なる文字数が1つ減る）
del char_count[left_char]
left += 1 # ウィンドウの左端を右に1つ動かす
# 現在のウィンドウ[s[left:right+1]]は異なる文字数がK個以内に収まっている
# ウィンドウのサイズ（right - left + 1）がこれまでの最大より大きければ更新
current_length = right - left + 1
if current_length > max_length:
max_length = current_length
longest_substr = s[left:right+1]
# 見つかった最長の部分文字列を返す（長さではなく文字列そのものを返す実装）
return longest_substr
# 使用例:
print(longest_substring_at_most_k_distinct("abcbdbdbbdcdabd", 2)) # 出力: "bdbdbbd"