Minimum Window Substring
2つの文字列、sとtが与えられます。繰り返しも考慮して、tのすべての文字を含むsの最短部分文字列を見つけてください。たとえば、tに同じ文字が2回含まれている場合、部分文字列にもその文字が少なくとも2回含まれていなければなりません。文字の順序は問いません。また、ほかの文字が含まれていてもかまいません。
最短の部分文字列が複数ある場合は、最も左にあるものを返してください。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とは異なる文字です。小文字のcを含む部分文字列はないため、答えは空文字列です。
発展問題
tの文字数が少なく、sが長い場合、sのほとんどは関係ありません。ウィンドウがtの文字がある位置の間だけを移動するようにできますか？
ヒント
1つずつ開いてください。開くたびに少しずつ答えに近づきます。
tをすべて含むウィンドウは長くしても引き続きすべてを含み、何かが欠けているウィンドウは短くしても引き続きそれが欠けたままです。この性質を利用すれば、すべての開始位置とすべての終了位置の組み合わせを試さずに済みます。右端を前方に動かし、ウィンドウが
tを含むようにします。次に、ウィンドウが引き続きtを含む間、左端を前方に動かし、その都度記録します。どちらの端も後ろに動かす必要はありません。ウィンドウが各文字をあと何個必要としているかを表す表と、不足している個数の合計を表す数値
missingを保持します。文字が入ってきたとき、その文字がまだ必要であればmissingを減らし、文字が出ていくとき、ウィンドウ内でその文字が不足することになればmissingを増やします。missingが 0 のとき、ウィンドウはtをちょうどカバーしています。
解説
重要なのはウィンドウ内の文字数であり、その順序ではありません。ウィンドウがtを含むまで右端を動かし、含んだ状態を保てる間は左端を動かします。どちらの端も戻りません。不足している文字数を数えるカウンターを使えば、ウィンドウがtを含んでいるかどうかを一度に判定できます。
各開始位置からウィンドウを拡大する
正しいが、最大のテストでは終わらない
考え方
開始位置を固定し、各文字の出現数を数えながら、ウィンドウを一度に1文字ずつ広げます。各ステップの後に、t が使う u 種類の文字をそれぞれ確認します。条件を満たす最初の終端位置が、この開始位置からの最短の被覆ウィンドウになるため、そこで止めます。開始位置は左から右へ進め、最短のウィンドウより厳密に短い場合にのみ最良の結果を更新するため、同じ長さなら最も左のものが残ります。
ウィンドウが存在しない場合は、すべての開始位置で s の末尾まで読み進めます。ステップ数は約 n²/2 で、n = 5 × 10^4 のとき 1.25 × 10^9 になります。
アルゴリズム
tが要求する各文字の個数を数えます。- 各
startについて、カウント表をクリアし、endを右に進めながらs[end]を追加します。 - ウィンドウに各文字が十分に含まれている場合、最良のものより厳密に短ければそれを保持し、次の start に進みます。
- 最良のウィンドウを返します。どのウィンドウも
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]すべての文字を確認するスライディングウィンドウ
考え方
カバーしているウィンドウに文字を追加してもカバーしたままであり、何かを見落としているウィンドウから文字を削除しても見落としたままです。したがって、開始位置が右に移動すると、最短のカバーウィンドウの終了位置が左に戻ることはありません。
見落とされるウィンドウはありません。最良のウィンドウをLからRまでとします。rightがRに到達する前にleftがLを越えるには、Lから始まるより短いウィンドウがtをカバーしていなければなりません。したがって、rightがRに到達すると、縮小によってleftはLまで進み、そのウィンドウが記録されます。
各端点は最大n回移動しますが、各チェックでは最大u個のカウントを読み取ります。計算量はO(n·u)です。
アルゴリズム
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を過不足なく含んでいます。
needが0より大きい文字が入ると、不足分が埋まるため、missingは減ります。文字を取り除いた結果、その文字のneedが0より大きくなると、不足分が生じるため、missingは増えます。余分な文字は影響しません。t = aanの場合、bananaではmissingが最初に0になるのはbanaで、余分なbを取り除いても、anaは引き続き条件を満たします。
各文字の追加と削除はそれぞれ1回で、一定のコストで行えます。時間計算量はO(n + m)で、128個のカウントを持つテーブルを1つ使います。
アルゴリズム
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にはaが2つ必要なので、banでは足りない。 - 文字がウィンドウに入るときや出るときに、毎回
missingを変更する。すると余分なaも数えられ、ウィンドウにnがないのにmissingが0になることがある。 - 長さが同じ場合に最良のウィンドウを置き換える。2つ目の例では、これによりインデックス3の
anaが返される。 - 「見つからない」場合の長さに
nを使う。答えがs全体の場合、その長さもnなので、n+1から始める。 c - 'a'をインデックスに使う26スロットのテーブル。3つ目の例のような大文字は、その範囲外になる。
よくある質問3
Minimum Window Substring の時間計算量は何ですか？
欠損カウンター方式のウィンドウは、n と m がそれぞれ s と t の長さであるとき、O(n + m) 時間で実行されます。テーブルの構築では t を1回読み取り、s の各文字はウィンドウに入るのも出るのも最大1回です。追加メモリは文字コードごとに1つのカウントです。
なぜ左端は決して戻らないのでしょうか？
左端がある位置を通過するのは、そこから始まるウィンドウがtをカバーした後だけであり、そのウィンドウはその開始位置からの最短のカバー区間でした。そこから始まり、より後で終わるウィンドウはどれも長くなるため、戻ってもより良い答えは決して見つかりません。
最小ウィンドウ部分文字列は、文字列内のアナグラムを見つけることとどう違いますか？
アナグラムはtの文字をちょうど含むため、そのウィンドウの長さは固定のmで、一度に1ステップずつスライドします。ここでは余分な文字が許されるため、長さも答えの一部です。ウィンドウはtを含むまで広がり、含み続ける間は縮みます。
def minWindow(s, t):
# ここにコードを書いてくださいテスト #1
テスト #2
テスト #3
引数
s = "mappingtheplan" t = "nap"
期待される出力
"plan"