Minimum Window Substring
2つの文字列 s と t が与えられます。t のすべての文字を含む s の最短部分文字列（連続する文字の並び）を見つけてください。文字の重複も数えます。つまり、t に同じ文字が2回含まれている場合、部分文字列にもその文字が少なくとも2回含まれている必要があります。文字の順序は問いません。また、部分文字列にほかの文字が含まれていてもかまいません。
複数の部分文字列の長さが同じ最短である場合は、最も左にあるものを返してください。s のどの部分文字列にも t のすべての文字が含まれていない場合は、空文字列を返してください。
関数
- sstring
- 検索対象の文字列
- tstring
- ウィンドウに含める必要がある文字（重複を含む）
- 戻り値string
- s のすべての t を含む部分文字列のうち、最短で、次に最も左にあるもの、または空文字列
制約
1 ≤ s.length ≤ 5 × 1041 ≤ t.length ≤ 104sとtには英字のみが含まれます。大文字と小文字は異なる文字です。- 最短の部分文字列が複数ある場合、答えは最も左にあるものです。存在しない場合は
""です。
例
- 入力
- s = "mappingtheplan"t = "nap"
- 出力
- "plan"
- 説明
- 左から読むと、
n、a、pを含む最初のウィンドウはappinで、5文字の長さです。末尾のplanは4文字ですべてを含み、3文字の連続した部分にはそのようなものはありません。
- 入力
- s = "banana"t = "aan"
- 出力
- "ana"
- 説明
tはaを2つ、nを1つ求めます。インデックス1のanaがちょうどそれに当たります。2つ目のanaはインデックス3から始まり、左端のものが優先されます。
- 入力
- s = "Coddy"t = "cd"
- 出力
- ""
- 説明
Coddyの中の C は大文字だけで、大文字と小文字は異なる文字です。小文字のcを含む部分文字列はないため、答えは空文字列です。
提出時に隠しテスト+17件
発展問題
t が使う文字がわずかで s が長い場合、s の大部分は関係しません。t の文字を含む位置の間だけをウィンドウが飛び移るようにできますか？
ヒント
1つずつ開いてください。開くたびに少しずつ答えに近づきます。
t全体を含むウィンドウは長くしても引き続き含み、何かが欠けているウィンドウは短くしても引き続き欠けたままです。この性質を利用して、すべての開始位置とすべての終了位置の組み合わせを試すのを避けましょう。ウィンドウが
tを含むまで右端を前方へ移動します。次に、ウィンドウがまだtを含んでいる間、左端を前方へ移動し、その都度記録します。どちらの端も後ろへ戻す必要はありません。ウィンドウが各文字をあと何個必要としているかを表で管理し、全体で不足している個数を示す数値
missingを1つ保持します。文字がウィンドウに入ったとき、それがまだ必要な文字である場合にのみmissingを減らします。文字がウィンドウから出たとき、その文字が不足する場合にのみmissingを増やします。missingが0のとき、ウィンドウはtをちょうど満たしています。
解説
答えを左右するのは、ウィンドウ内の各文字の個数であり、文字の順序ではありません。また、最適なウィンドウはどこからでも始められます。すべての開始位置について、すべての終了位置を試すと、ウィンドウの数は O(n²) になります。解決の鍵は、両端が前方にしか動かないウィンドウです。右端を広げて t を含むまで伸ばし、含んだ状態が続く間は左端を縮めます。そして、不足している文字の数を表すカウンターが1つあれば、t を含んでいるかどうかを一度に判定できます。
すべての開始位置からウィンドウを拡大する
正しいが、最大のテストでは終わらない
考え方
부분 문자열이 시작되는 위치를 고정합니다. 그런 다음 한 번에 문자 하나씩 늘려 가며 내부의 각 문자가 몇 번 나오는지 세고, 매 단계마다 t를 포함하는지 확인합니다. 즉, t에서 사용하는 u개의 서로 다른 문자 각각에 대해, 윈도우에는 t에 있는 개수 이상이 포함되어야 합니다. 조건을 처음 만족하는 끝 위치가 이 시작 위치에서의 최소 포함 윈도우입니다. 같은 시작 위치에서 그보다 짧은 모든 윈도우는 먼저 확인되어 조건을 만족하지 못했기 때문입니다. 그 지점에서 멈춥니다.
모든 시작 위치에 대해 이 과정을 수행하고, 가장 짧은 윈도우를 유지します。開始位置は左から右へ試し、ウィンドウが現在の最良のものより厳密に短い場合にだけ置き換えるため、同じ長さのウィンドウでは最も左のものが残ります。
ウィンドウが長い場合や見つからない場合は処理が遅くなります。s にある唯一の Z が末尾にあり、t が 1 つ求めている場合、すべての開始位置で末尾まで読み取ります。ステップ数は約 n²/2 となり、n = 5 × 10^4 では 1.25 × 10^9 です。そのたびに最大 52 文字を確認します。ウィンドウがまったく存在しない場合も同様です。
アルゴリズム
tが各文字を何個ずつ要求しているかを数え、使われている文字を一覧にします。- 各
startについて、カウント表をクリアし、endをstartからsの末尾まで動かしながら、s[end]を表に追加します。 - 追加するたびに、
tの各文字を確認します。ウィンドウ内に各文字が十分に含まれている場合は、その長さをこれまでの最良のものと比較し、厳密に短ければ採用して、探索を止めます。 - すべての開始位置を調べたら、最良のウィンドウを返します。どのウィンドウも
tを満たさなかった場合は、""を返します。
def minWindow(s, t):
need = [0] * 128 # copies of each character code that t asks for
for ch in t:
need[ord(ch)] += 1
letters = [c for c in range(128) if need[c] > 0]
best_start, best_len = 0, len(s) + 1
for start in range(len(s)):
have = [0] * 128 # counts inside s[start..end]
for end in range(start, len(s)):
have[ord(s[end])] += 1
if all(have[c] >= need[c] for c in letters):
# The first end that covers t gives the shortest window from this start.
if end - start + 1 < best_len:
best_start, best_len = start, end - start + 1
break
if best_len > len(s):
return ""
return s[best_start:best_start + best_len]すべての文字をチェックするスライディングウィンドウ
考え方
2つの事実により、最初からやり直す必要はありません。tを含むウィンドウに文字を追加しても、引き続き含んだままです。また、何かを含まないウィンドウから文字を削除しても、含まないままです。そのため、開始位置を右に動かすとき、tを含む最短ウィンドウの終端は、その位置にとどまるか右に動くことしかありません。両端を一緒に前へ進めることができ、どちらも後戻りしません。
rightをs上で動かし、各文字を出現回数の表に加えます。ウィンドウがtを含むたびに、それを候補とします。これまでの最良のものより短ければ記録し、その後s[left]を取り除いてleftを前に進め、もう一度確認します。ウィンドウがtを含まなくなるまでこれを繰り返し、その後、右側を伸ばす処理に戻ります。
見落とされるウィンドウはありません。LからRまでの最良のウィンドウを考えてみましょう。rightがRに達する前にleftがLを通り過ぎていたとすると、Lから始まりRより前で終わるウィンドウの中にtを含むものがあり、それは最良のウィンドウより短いはずです。したがって、rightがRに達すると、縮小ループはleftをLまで進め、最良のウィンドウを記録します。それぞれの端が動く回数は最大でもn回ですが、確認のたびにu個までの出現回数を読み取ります。これはtで使われる文字それぞれについての回数であり、前回の確認から変化した回数は1つだけであるにもかかわらずです。
アルゴリズム
tが要求する各文字の個数を数え、その文字を列挙します。空のウィンドウ、left = 0、最良の長さをn+1として開始します。- すべてのインデックスについて
rightを進め、s[right]をウィンドウの個数に加えます。 tのすべての文字がウィンドウ内に必要な個数だけ含まれている間、ウィンドウの長さが最良の長さより厳密に短ければ記録し、個数からs[left]を削除してleftを進めます。- 最良の長さがまだ
n+1なら""を返し、そうでなければ最良のウィンドウを返します。
def minWindow(s, t):
need = [0] * 128 # copies of each character code that t asks for
for ch in t:
need[ord(ch)] += 1
letters = [c for c in range(128) if need[c] > 0]
have = [0] * 128 # counts inside s[left..right]
def covers():
for c in letters:
if have[c] < need[c]:
return False
return True
left = 0
best_start, best_len = 0, len(s) + 1
for right in range(len(s)):
have[ord(s[right])] += 1 # expand on the right
while covers(): # shrink from the left while the window still covers t
if right - left + 1 < best_len:
best_start, best_len = left, right - left + 1
have[ord(s[left])] -= 1
left += 1
if best_len > len(s):
return ""
return s[best_start:best_start + best_len]不足カウンターを使ったスライディングウィンドウ
考え方
同じウィンドウを使い、条件を1つの数値に置き換えます。need[c]を、tが必要とするcの個数からウィンドウ内にある個数を引いた値とします。正の値はウィンドウにまだ不足分があることを、負の値は余分に含まれていることを意味します。missingはウィンドウに不足している文字の合計個数とし、初期値はtの長さです。missingが0のとき、ウィンドウはtを過不足なく含みます。
更新にかかる処理は1ステップです。s[right]が入るとき、その文字のneedが0より大きければ不足分を埋めるため、missingは1減ります。いずれの場合もneedは1減り、余分な分として0未満になることもあります。s[left]が出ると、needは1増えます。その結果、0より大きくなった場合、ウィンドウからtが必要とする文字が1つ失われたことになるため、missingは1増えます。余分な文字が入ったり出たりしても、missingには影響しません。
s = banana、t = aanをたどってみましょう。最初のneedはaが2、nが1で、missingは3です。bは必要ありません。最初のaでmissingは2になり、nで1、2つ目のaで0になるため、banaはtを含みます。ウィンドウを縮めると、余分なbが取り除かれてanaが残ります。これは3文字で、ここまでの最短です。そのaを取り除くと、missingは1に戻ります。最後のaが入ると、nanaで再び条件を満たし、ウィンドウを縮めると2つ目のanaになります。これより短くはないため、最も左にあるanaが残ります。
sの各文字はウィンドウに1回入り、出るのは最大1回で、各移動にかかる処理量は一定です。needの構築ではtを1回読み取ります。全体の処理時間はO(n + m)で、追加メモリは128個のカウントを持つ表だけです。
アルゴリズム
needにtの各文字の出現回数を設定し、missingをtの長さ、left = 0、最短の長さをn+1に設定します。- 各
rightについて、need[s[right]]が 0 より大きければmissingを減らし、その後need[s[right]]を減らします。 missingが 0 の間、ウィンドウの長さが最短の長さより厳密に短ければ、そのウィンドウを記録します。次にneed[s[left]]を増やし、その値が 0 より大きくなった場合はmissingを増やします。leftを進めます。- 最短のウィンドウを返します。最短の長さがまだ
n+1の場合は、""を返します。
def minWindow(s, t):
# need[c]: copies of c that t asks for minus copies inside the window.
# Positive means the window still lacks c; negative means it holds spares.
need = [0] * 128
for ch in t:
need[ord(ch)] += 1
missing = len(t) # characters of t the window does not cover yet
left = 0
best_start, best_len = 0, len(s) + 1
for right in range(len(s)):
c = ord(s[right])
if need[c] > 0: # this copy fills a gap
missing -= 1
need[c] -= 1
while missing == 0: # the window covers t: record it, then shrink
if right - left + 1 < best_len:
best_start, best_len = left, right - left + 1
c = ord(s[left])
need[c] += 1
if need[c] > 0: # gave away a copy t needs
missing += 1
left += 1
if best_len > len(s):
return ""
return s[best_start:best_start + best_len]
落とし穴と境界ケース
誤答の多くは、数える対象を間違えるか、ウィンドウを記録するタイミングを間違えています。
- コピーではなく文字を数えている。
t = aanには2つのaが必要なので、banでは条件を満たしません。 - 入ってくる文字ごとに
missingを減らしている。3つ目のaは余分な文字です。これによってmissingを減らすと、ウィンドウにnがまだないのにカウンターが0になります。needが0より大きかった場合にのみ減らしてください。 - 出ていく文字ごとに
missingを増やしている。余分な文字を取り除いても、ウィンドウは引き続きtを含んでいます。needが0より大きくなった場合にのみ増やしてください。 - 縮小ループの後にウィンドウを記録している。その時点では、ウィンドウはもう
tを含んでいません。ループ内で、s[left]を取り除く前に記録してください。 - 新しいウィンドウが同じ長さの場合に、最良のウィンドウを置き換えている。そうすると、最短のウィンドウのうち最も右にあるものが返されます。厳密な小なりで比較してください。
- 「見つからない」場合の長さとして
nを使っている。答えがs全体の場合、その長さもnです。2つのケースを区別できるよう、n+1から始めてください。 c - 'a'をインデックスに使う26個のスロットのテーブルを使っている。大文字はその範囲外になります。文字コードごとに1つのスロットを使ってください。
よくある質問4
Minimum Window Substring の時間計算量は何ですか？
不足数カウンターを使ったスライディングウィンドウは、n と m がそれぞれ s と t の長さであるとき、O(n + m) 時間で実行されます。テーブルの構築では t を1回読み取り、s の各文字は固定コストでウィンドウに入るのも出るのも最大1回です。追加メモリとして、文字コードごとに1つのカウントを持つテーブルが必要ですが、これは入力サイズに応じて増加しません。
なぜ左端は決して後ろに戻らないのでしょうか？
左端がある位置を通り過ぎるのは、そこから始まるウィンドウが t をカバーした後だけであり、そのウィンドウはその開始位置からの最短のカバーウィンドウです。そこから始まってさらに後で終わるウィンドウはどれもそれより長いため、戻ってもより良い答えは決して見つかりません。これが、両端が一度だけ前方へ進み、処理が線形時間に収まる理由です。
欠けているカウンターは何を数えますか？
これは、ウィンドウ内にまだ存在しない、t が要求する文字のコピー数であり、need の正の値の合計です。t の長さから始まり、ウィンドウが t を含むときに限り 0 になります。余分なコピーでは値は変化しません。そのため、すべての文字を走査する代わりに、1 回の比較で済みます。
Minimum Window Substringは、文字列内のアナグラムを見つけることとどう違いますか？
アナグラムはtの文字だけを過不足なく含むため、ウィンドウの長さはmに固定され、1ステップずつスライドします。一方、このウィンドウには余分な文字が含まれることがあるため、その長さも答えの一部になります。tを覆うまで右側に広げ、覆った状態を保てる間は左側を縮めます。
Python
def minWindow(s, t):
# ここにコードを書いてくださいケース1
ケース2
ケース3
入力
s = "mappingtheplan" t = "nap"
期待値
"plan"