部分文字列のスライディングウィンドウ
可変サイズのスライディングウィンドウを実装し、重複文字のない最長部分文字列や、対象文字をすべて含む最小ウィンドウを求めます。
「部分文字列のスライディングウィンドウ」はCoddyKit上の無料Coding Interview Prepレッスンです。 これはレッスン2/4です。 下記で完全なレッスンを無料で読むことができます。その後、ブラウザ内の組み込みコードエディタと24時間対応のAIチューターでハンズオン演習できます。 これはCoding Interview Prep学習パスの一部であり、ウェブとCoddyKitアプリ全体で進捗が同期されます。 Coding Interview Prepコースには全4レッスンが含まれています。
スライディングウィンドウの概念
スライディングウィンドウは、左ポインタと右ポインタの間にある部分配列（または部分文字列）を管理します。考えられるすべての部分配列の性質をO(n²)で毎回最初から計算する代わりに、ウィンドウを1要素追加して右に広げ、1要素削除して左から縮めながら、各ステップで実行中の状態をO(1)で維持します。その結果、アルゴリズム全体をO(n)で実行できます。配列を後戻りせずに前方へ移動するため、このウィンドウは「スライディング」と呼ばれます。
# Fixed-size window sum: O(n) after O(k) setup
def max_sum_window(nums, k):
window_sum = sum(nums[:k]) # initial window
best = window_sum
for i in range(k, len(nums)):
window_sum += nums[i] # add new right
window_sum -= nums[i - k] # remove old left
best = max(best, window_sum)
return best
print(max_sum_window([2,1,5,1,3,2], 3)) # 9 ([5,1,3])固定サイズと可変サイズのウィンドウ
スライディングウィンドウには2種類あります。固定サイズのウィンドウでは、両方のポインタが同じペースで進み、ウィンドウには常にちょうどk個の要素が含まれます。可変サイズのウィンドウでは、右ポインタを貪欲に進め、ウィンドウが制約に違反した場合にだけ左ポインタを進めて縮めます。可変サイズのウィンドウは、最適なウィンドウサイズがあらかじめ分からない「重複する文字のない最長部分文字列」のような問題を解決します。
# Variable window: longest substring with at most k distinct chars
def longest_k_distinct(s, k):
from collections import defaultdict
freq = defaultdict(int)
left = 0
best = 0
for right in range(len(s)):
freq[s[right]] += 1
while len(freq) > k: # window invalid: shrink
freq[s[left]] -= 1
if freq[s[left]] == 0:
del freq[s[left]]
left += 1
best = max(best, right - left + 1)
return best
print(longest_k_distinct('eceba', 2)) # 3 ('ece')
print(longest_k_distinct('aa', 1)) # 2重複のない最長部分文字列
これは、可変サイズのスライディングウィンドウで最も有名な問題です。現在のウィンドウ内の文字を追跡するために集合を使います。右側を広げ、重複する文字が見つかったら、その文字が取り除かれるまで左側から縮めます。より高速な方法では、各文字の最新のインデックスをハッシュマップに保存します。これにより、左ポインタを少しずつ進めるのではなく、重複文字の先まで一度に移動できます。
def length_of_longest_substring(s):
char_idx = {} # char -> last seen index
left = 0
best = 0
for right, c in enumerate(s):
if c in char_idx and char_idx[c] >= left:
left = char_idx[c] + 1 # jump past duplicate
char_idx[c] = right
best = max(best, right - left + 1)
return best
print(length_of_longest_substring('abcabcbb')) # 3 ('abc')
print(length_of_longest_substring('bbbbb')) # 1
print(length_of_longest_substring('pwwkew')) # 3 ('wke')最小ウィンドウ部分文字列
文字列sとtが与えられたとき、tのすべての文字を含むs内の最小のウィンドウを求めます。2つの頻度マップを使います。needは必要な文字を、haveは現在のウィンドウ内で必要数を満たしている文字を表します。tに含まれる異なる文字のうち、条件を満たしている数を（formedカウンタで）追跡します。右側を広げて文字を含め、tのすべてがカバーされたら、ウィンドウが最小になるまで左側を縮めます。計算量はO(|s| + |t|)です。
from collections import Counter
def min_window(s, t):
if not t or not s: return ''
need = Counter(t)
have = {}
formed = 0
required = len(need)
left = 0
best = float('inf'), 0, 0
for right, c in enumerate(s):
have[c] = have.get(c, 0) + 1
if c in need and have[c] == need[c]:
formed += 1
while formed == required:
if right - left + 1 < best[0]:
best = right - left + 1, left, right
have[s[left]] -= 1
if s[left] in need and have[s[left]] < need[s[left]]:
formed -= 1
left += 1
return s[best[1]:best[2]+1] if best[0] != float('inf') else ''
print(min_window('ADOBECODEBANC', 'ABC')) # 'BANC'スライディングウィンドウのテンプレート
可変サイズのスライディングウィンドウ問題の多くは、同じテンプレートに従います。右側を広げて新しい文字を含め、ウィンドウの状態を更新し、有効性を確認します。無効であれば、再び有効になるまで左側から縮めます。重要な点は、左ポインタは前に進むだけで、後戻りしないことです。そのため、すべての縮小処理を合わせた計算量はO(n)になります。ウィンドウ内の各要素を訪れる回数は最大2回（1回追加し、1回削除）です。
def sliding_window_template(s, condition_check, update_state, remove_state):
"""
Generic sliding window skeleton.
Adapt condition_check, update_state, remove_state per problem.
"""
left = 0
state = {} # or whatever state you need
best = 0
for right in range(len(s)):
update_state(state, s[right]) # expand window
while not condition_check(state): # window invalid
remove_state(state, s[left]) # shrink window
left += 1
best = max(best, right - left + 1)
return best文字列内の順列
パターンpの順列がsの部分文字列として存在するかを確認します。順列の判定は、pと同じ文字頻度を持つウィンドウを探すことと同じです。len(p)文字の固定サイズのスライディングウィンドウを維持し、頻度を比較します。各ステップでCounterオブジェクト全体を比較する計算量はO(26)（英小文字の場合は定数）なので、全体の計算量はO(n × 26) = O(n)です。
from collections import Counter
def check_inclusion(p, s):
if len(p) > len(s): return False
need = Counter(p)
window = Counter(s[:len(p)])
if need == window: return True
for right in range(len(p), len(s)):
left = right - len(p)
window[s[right]] += 1
window[s[left]] -= 1
if window[s[left]] == 0:
del window[s[left]]
if window == need:
return True
return False
print(check_inclusion('ab', 'eidbaooo')) # True ('ba')
print(check_inclusion('ab', 'eidboaoo')) # Falseアナグラム部分文字列: すべてを数える
s内にある、pのアナグラムの開始インデックスをすべて求めます。これは「文字列内の順列」と同じ固定サイズのウィンドウ技法ですが、最初の一致でTrueを返す代わりに、一致した位置をすべて集めます。ウィンドウのサイズはlen(p)に固定し、s全体をスライドさせながら各ステップで頻度を比較します。
from collections import Counter
def find_anagrams(s, p):
result = []
need = Counter(p)
k = len(p)
window = Counter(s[:k])
if window == need:
result.append(0)
for right in range(k, len(s)):
window[s[right]] += 1
left_char = s[right - k]
window[left_char] -= 1
if window[left_char] == 0:
del window[left_char]
if window == need:
result.append(right - k + 1)
return result
print(find_anagrams('cbaebabacd', 'abc')) # [0, 6]異なる文字が最大2個の最長部分文字列
これはスライディングウィンドウの応用です。異なる文字を最大2個含む最長の部分文字列を求めます。現在のウィンドウ内の文字の頻度マップを維持します。マップのエントリ数が2を超えたら、制約が再び満たされるまで左ポインタを右へ移動します（頻度を減らし、0になったら削除します）。これは「異なる文字が最大k個」のk=2の場合にあたります。
def longest_substring_two_distinct(s):
from collections import defaultdict
freq = defaultdict(int)
left = 0
best = 0
for right, c in enumerate(s):
freq[c] += 1
while len(freq) > 2:
freq[s[left]] -= 1
if freq[s[left]] == 0:
del freq[s[left]]
left += 1
best = max(best, right - left + 1)
return best
print(longest_substring_two_distinct('eceba')) # 3 ('ece')
print(longest_substring_two_distinct('ccaabbb')) # 5 ('aabbb')スライディングウィンドウの最大値
サイズkのすべてのウィンドウについて、最大値を求めます。各ウィンドウの最大値を総当たりで調べるとO(n×k)かかります。最適な方法では、インデックスを格納する単調デックを使います。値が降順になるようにデックを維持することで、先頭には常に現在のウィンドウの最大値のインデックスが置かれます。ウィンドウから外れたインデックスは先頭から削除し、大きな要素が入ってきたときは末尾からインデックスを削除します。全体の計算量はO(n)です。
from collections import deque
def max_sliding_window(nums, k):
dq = deque() # stores indices, decreasing values
result = []
for i, n in enumerate(nums):
# Remove indices outside window
while dq and dq[0] < i - k + 1:
dq.popleft()
# Maintain decreasing order
while dq and nums[dq[-1]] < n:
dq.pop()
dq.append(i)
if i >= k - 1: # window is full
result.append(nums[dq[0]])
return result
print(max_sliding_window([1,3,-1,-3,5,3,6,7], 3))
# [3, 3, 5, 5, 6, 7]スライディングウィンドウを使う場面
次のような条件が見えたら、スライディングウィンドウを検討してください:
- 制約のある部分文字列・部分配列（最大長、合計 = k、異なる文字が最大k個）
- 集約処理を行う固定サイズのウィンドウ（最大値、合計、頻度）
- 連続した範囲に関する問題（任意の部分集合ではないもの）
# Recognising sliding window problems:
# 1. Fixed window: 'maximum average of subarray of length k'
def max_avg(nums, k):
s = sum(nums[:k])
best = s
for i in range(k, len(nums)):
s += nums[i] - nums[i-k]
best = max(best, s)
return best / k
print(max_avg([1,12,-5,-6,50,3], 4)) # 12.75
# 2. Variable window: 'smallest subarray with sum >= target'
def min_sub_len(target, nums):
left = s = 0
best = float('inf')
for right, n in enumerate(nums):
s += n
while s >= target:
best = min(best, right - left + 1)
s -= nums[left]; left += 1
return 0 if best == float('inf') else best
print(min_sub_len(7, [2,3,1,2,4,3])) # 2有効なウィンドウの数え上げ: 最大K個
条件を満たす部分配列の数を求める問題があります。便利な方法は、異なる文字が最大k個の部分配列を数え、それを引いてちょうどk個を求めることです: exactly(k) = at_most(k) - at_most(k-1)。at_mostの各呼び出しはO(n)なので、全体の計算量もO(n)です。at_most関数は、異なる文字の数がkを超えないウィンドウを、right - left + 1を合計することで数えます（各rightに対して有効なleftの始点がすべて含まれます）。
from collections import defaultdict
def subarrays_at_most_k(s, k):
freq = defaultdict(int)
left = 0
count = 0
for right, c in enumerate(s):
freq[c] += 1
while len(freq) > k:
freq[s[left]] -= 1
if freq[s[left]] == 0: del freq[s[left]]
left += 1
count += right - left + 1 # all valid windows ending at right
return count
def subarrays_exactly_k(s, k):
return subarrays_at_most_k(s, k) - subarrays_at_most_k(s, k-1)
print(subarrays_exactly_k('araaci', 2)) # 9理解度チェック
このレッスンのData Structures & Algorithms — Coding Interview Prepの概念について、理解度を確認しましょう。
レッスンのまとめ
このレッスンでは、次のことを学びました: スライディングウィンドウは、要素が追加・削除されるときにO(1)で更新できる実行中のウィンドウ状態を維持することで、O(n²)を解消します。また、固定サイズのウィンドウでは両方のポインタが同じペースで進み、可変サイズのウィンドウでは右側を貪欲に広げ、制約に違反したときだけ左側を縮めます。さらに、最小ウィンドウ部分文字列と文字列内の順列は、頻度マップによるウィンドウ状態を使い、現在条件を満たしている必要な文字の数をカウンタで追跡します。次は、アナグラムと文字頻度マップについて学びます。
よくある質問
「部分文字列のスライディングウィンドウ」レッスンは無料ですか？
はい。「部分文字列のスライディングウィンドウ」の完全なテキストはこのウェブで無料で読めます。インタラクティブに演習し（組み込みコードエディタと24時間対応のAIチューター）、Coding Interview Prepコースの残りをアンロックするには、CoddyKit PROにアップグレードしてください。 Coding Interview Prepコースには全4レッスンが含まれています。
「部分文字列のスライディングウィンドウ」で何を学びますか？
可変サイズのスライディングウィンドウを実装し、重複文字のない最長部分文字列や、対象文字をすべて含む最小ウィンドウを求めます。 ブラウザで直接実行するハンズオンコードでCoding Interview Prepを演習し、24時間対応のAIチューターがレッスンを進める中での質問に答えます。
Coding Interview Prepを始めるのに経験は必要ですか？
事前経験は必要ありません。CoddyKitのCoding Interview Prepは初級者から上級者向けに構成されているため、ここから始めるか最初から始めて、自分のペースで進むことができます。 これはレッスン2/4です。
「部分文字列のスライディングウィンドウ」レッスンにはどのくらい時間がかかりますか？
ほとんどのCoddyKitレッスンは約5～10分かかります。各レッスンはコンパクトでインタラクティブなので、着実に進歩し、ウェブとアプリ全体で正確に前回の場所から再開できます。
このCoding Interview Prepレッスンでコードを書いて実行できますか？
はい。すべてのCoding Interview Prepレッスンに組み込みコードエディタが含まれているため、ブラウザでリアルコードを書いて実行し、即座のAIフィードバックを取得できます。ローカル設定は不要です。
このコースのすべてのレッスン
- 面接のためのPython文字列API
- 部分文字列のスライディングウィンドウ
- アナグラムと文字頻度マップ
- 文字列のエンコード、反転、回文