問題と適用場面
文字列 s と t が与えられたとき、t のすべての文字を t に出現する回数以上含む、s の最短の連続部分文字列を見つけます。大文字と小文字は区別されます。例えば：
s = "ADOBECODEBANC"
t = "ABC"
output = "BANC"t = "AABC" の場合、候補となるウィンドウには少なくとも 2 つの A、1 つの B、および 1 つの C が必要です。集合の要素判定（set-membership）だけではこの出現回数の要件が失われてしまいます。これは本問における最も典型的な意味論的誤りです。
制約は 1 <= s.length, t.length <= 100000 であり、両方の文字列には英大文字と英小文字のみが含まれます。 解が存在する場合、最短の解は一意です。t を満たすウィンドウが存在しない場合は空文字列を返します。以下の実装では、標準的な制約外の入力ではありますが、空の t や t より短い s も防御的に処理しています。
近年のソフトウェアエンジニアリング面接の公開記録でも Minimum Window Substring は依然として出題されており、t に重複文字がない変種も含まれます。英語圏・中国語圏のコーディングプラットフォームでも本問は定番です。その核心となるスキルは、グローバルな最小区間探索をインクリメンタルに維持される状態へと変換することにあるため、正確な分類は coding です。例示のプログラミング言語によってこの分類が変わることはありません。
面接官が見ているポイント
第 1 の評価基準は、正確なモデリングです。優れた回答では、「t を含む」ことを出現頻度の制約として表現します。すなわち、すべての対象文字 c について、現在のウィンドウが window[c] >= need[c] を満たす必要があります。単に対象文字がすべて現れたと表現するだけでは、t = "AA" を正しく扱えません。
第 2 の評価基準は、2 乗のベースラインの背景にある単調性（monotonicity）を認識できるかです。右端を右に進めると文字が追加されるだけなので、有効なウィンドウは拡大しても有効なままです。右端を固定した場合、左端を進めると文字が取り除かれます。ウィンドウが一旦有効になれば、無効になる直前まで縮小させることができ、その過程でより短い候補を記録できます。
第 3 の評価基準は、有効性チェックの軽量化です。ポインタを動かすたびに頻度テーブル全体をスキャンしていては、線形時間の計算量を達成できません。実装では、必要な頻度を満たした対象文字種の数を表す formed を用い、required = need.size とします。formed は、ある文字の頻度が初めて要求数に達したときに増加し、文字の除外によって要求数を下回ったときに減少します。過剰な文字があっても 2 重にカウントされることはありません。
最後に、正当性と境界条件の根拠を説明できる必要があります。なぜ各右端に対する最短の有効ウィンドウが漏れなく調べられるのか、なぜ破棄された左端が将来より良い候補を作ることがないのか、そしてなぜ各ポインタが最大で s.length 回しか移動しないのかを示します。
回答前に明確にすべき質問
- 大文字と小文字は区別されますか？ 本問では区別します。区別しない場合は、まず正規化を定義する必要があります。正規化により元の文字列のインデックスへのマッピングが変わる可能性があります。
- 「含む」とは
tの文字の順序を保持する必要がありますか？ いいえ。本問では出現頻度の一致のみが求められます。順序も要求される場合は Minimum Window Subsequence（最小ウィンドウ部分列）問題となり、今回の有効性判定条件は適用できません。 - ターゲット内の重複文字は個別にカウントしますか？ はい。
t = "AABC"には 2 つのA文字が必要であり、これが頻度マップを用いる直接の動機となります。 - 最短のウィンドウが複数タイになった場合はどうしますか？ 標準的な問題設定では一意性が保証されています。その保証がない場合、本実装では厳密に小さい長さの場合にのみ更新するため、最も先に出現した最短ウィンドウを返します。
- 文字セットは何ですか？ 入力は英文字であるため、JavaScript の UTF-16 コードユニットのインデックス走査で有効な文字が分断されることはありません。任意の Unicode の場合は、コードポイント単位で照合するのか、ユーザーが認識する書記素クラスタ（grapheme clusters）単位で照合するのかを事前に定義する必要があります。
- いずれかの文字列が空になることはありますか？ 標準の制約では空文字列は除外されます。サンプルの関数は、
tが空、sが空、またはs.length < t.lengthの場合に空文字列を返します。 - 関数はテキストとインデックスのどちらを返すべきですか？ 本問ではテキストを返します。インデックスを返す場合は、コアのスキャン処理を変えずに
[bestStart, bestStart + bestLength)を返します。
これらの質問は、有効性判定の述語、インデックス表現、または出力ルールに影響を与える可能性があります。言語の選択、変数名、具体的なハッシュマップの実装方法によってアルゴリズムの選択が変わることはありません。
30秒で伝える回答フレームワーク
「need の対象頻度をカウントし、2 つのポインタでウィンドウを管理します。右ポインタを広げる際、いずれかの文字種の頻度が初めて要求数に達したときにのみ formed を増やします。すべての文字種が満たされたら解を記録し、ウィンドウが無効になるまで左ポインタを進めます。これにより、各右端に対する最短の有効ウィンドウを調べることができます。両ポインタは右にしか進まないため、各位置の追加と削除は最大 1 回ずつとなり、時間計算量は O(|s| + |t|)、頻度マップの空間計算量は O(u) になります。」
ステップごとの詳細解説
ステップ 1：ベースラインから重複作業を明らかにする
各左端に対して、頻度を維持しながら右端を伸ばしていき、最初の有効なウィンドウで止めることができます。これによりすべての部分文字列を再カウントすることは避けられますが、各左端から s の大部分を再スキャンする可能性があり、O(|s|^2 + |t|) の時間がかかります。すべての部分文字列を一から再カウントすると 3 乗になる場合があります。
| アプローチ | 時間 | 追加空間 | 主なコスト |
|---|---|---|---|
| 各左端で拡大をやり直す | O(|s|^2 + |t|) | O(u) | 隣接する探索で同じ文字を何度も読み直す |
| 有効性チェックのたびに対象文字種を全スキャン | O(|s|u + |t|) | O(u) | 頻度テーブル全体の反復スキャン |
| スライディングウィンドウ＋条件達成文字種数カウント | O(|s| + |t|) | O(u) | 閾値の通過を正確に維持・管理する必要がある |
ここで u は t 内の異なる文字の種類数であり、英文字の制約下では最大 52 です。線形解法において重要なのは状態の設計であり、アルファベット数が小さいからといって不適切な有効性チェックを放置してよいわけではありません。
ステップ 2：O(1) での有効性チェックに必要な状態を定義する
need はターゲットの文字頻度を保持します。window は現在のウィンドウ内の対象文字の頻度を保持します。required = need.size は満たすべき文字種数であり、formed は要求頻度に達した文字種数です。ウィンドウが有効であることは、厳密に formed === required であることと同値です。
状態の更新は、要求数の閾値をまたぐタイミングと結びつける必要があります：
after adding c: window[c] changes from need[c]-1 to need[c], so formed += 1
after adding c: window[c] changes from need[c] to need[c]+1, so formed is unchanged
before removing c: window[c] equals need[c], so removal causes formed -= 1
before removing c: window[c] exceeds need[c], so removal leaves formed unchangedformed を対象文字の単純な合計数として扱ってしまうと、過剰な文字を二重カウントしやすくなります。上限を設けずに対象文字が出るたびにインクリメントすると、t = "AABC" を誤って早期にカバー済みと判定してしまいます。
ステップ 3：拡大・記録・縮小の順序を確定する
右ポインタは s[right] を取り込み、状態を更新します。ウィンドウが有効になったら、内部ループはまず [left, right] を解の候補として検討し、その後 s[left] の削除準備をします。削除によってある文字種が不足状態になる場合は、formed をデクリメントし、頻度を減らし、left を進めます。
削除の前に記録を行うことで、有効な候補のスキップを防ぎます。頻度を減らす前に等価性を判定することで、閾値遷移を明示的に捉えられます。先にデクリメントしてから要求数を下回ったかを判定する実装も可能ですが、解説と条件判定の順序は一致させる必要があります。
ステップ 4：線形スキャンを実装する
export function minWindow(s: string, t: string): string {
if (t.length === 0 || s.length < t.length) return "";
const need = new Map<string, number>();
for (const char of t) {
need.set(char, (need.get(char) ?? 0) + 1);
}
const window = new Map<string, number>();
const required = need.size;
let formed = 0;
let left = 0;
let bestStart = 0;
let bestLength = Number.POSITIVE_INFINITY;
for (let right = 0; right < s.length; right += 1) {
const char = s[right];
const target = need.get(char);
if (target !== undefined) {
const nextCount = (window.get(char) ?? 0) + 1;
window.set(char, nextCount);
if (nextCount === target) formed += 1;
}
while (formed === required) {
const length = right - left + 1;
if (length < bestLength) {
bestStart = left;
bestLength = length;
}
const leftChar = s[left];
const leftTarget = need.get(leftChar);
if (leftTarget !== undefined) {
const currentCount = window.get(leftChar) ?? 0;
if (currentCount === leftTarget) formed -= 1;
window.set(leftChar, currentCount - 1);
}
left += 1;
}
}
return Number.isFinite(bestLength)
? s.slice(bestStart, bestStart + bestLength)
: "";
}この実装では対象文字のカウントのみを保持します。対象外の文字もウィンドウの長さや左端の位置に影響を与えるため、事前に s から削除することはできません。単に頻度マップにエントリを設ける必要がないだけです。
ステップ 5：不変条件を述べ、正当性を証明する
外側ループの各イテレーション終了時に、以下の事実が成立します：
window[c]は、現在の区間[left, right]内の対象文字cの実際の出現数と一致する。formedは、window[c] >= need[c]を満たしている対象文字種の数と正確に一致する。- 内部ループが終了した後、現在のウィンドウは無効である。直前に調べた最後の有効ウィンドウが、その
right終端に対する最短の有効ウィンドウであった。 leftは右方向にしか進まない。すでに通過した以前の左端は、同じ右端に対してより長いウィンドウを形成するだけであり、後から右端を伸ばしても、その過去の左端で既に検討された候補より短くなることはない。
空の初期ウィンドウは最初の 2 つの不変条件を満たします。右の文字を追加するとその実際のカウントが更新され、閾値ルールによって 2 番目の不変条件が維持されます。ウィンドウが有効である間、アルゴリズムは各削除の前に候補を記録するため、最初の 2 つの不変条件が「ウィンドウが無効になった」と判定するまで、現在の right で終わるすべての有効な左端を漏れなく調べます。右端に関する帰納法により、アルゴリズムは各右端に対する最短の有効ウィンドウを調べます。全体としての最適解はこれら候補の中に必ず含まれるため、記録された解は正当です。
ステップ 6：重複文字を含むターゲットの追跡
s = "AAABBC" および t = "AABC" とします：
need = {A:2, B:1, C:1}, required = 3
right=0, A:1 formed=0
right=1, A:2 formed=1
right=2, A:3 formed=1 surplus A does not count twice
right=3, B:1 formed=2
right=4, B:2 formed=2 surplus B does not count twice
right=5, C:1 formed=3 [0,5] is valid
remove A at index 0: A:2, still valid; record [1,5] = "AABBC"
remove another A: A:1, formed falls to 2, so contraction stopsこのトレースにより、3 つの独立した詳細事項（1 より大きい要求頻度、要求数を超えた場合の重複カウントの防止、過剰分削除後の継続的な縮小）が確認できます。
ステップ 7：計算量を正確に分析する
need の構築で t を 1 回スキャンします。右ポインタは s を 1 回スキャンし、左ポインタは実行全体を通じて 0 から s.length まで 1 度だけ進みます。したがって、内側の while ループの累積処理量は O(|s|) です。マップ操作が平均 O(1) であるため、総時間計算量は O(|s| + |t|) です。2 つの頻度マップは最大で u 個の対象文字を保持するため、追加空間計算量は O(u) です。英文字の制約下では u <= 52 となります。
ステップ 8：オラクルと性質を用いたテスト検証
最低限、固定テストケースで以下を網羅すべきです：
("ADOBECODEBANC", "ABC") -> "BANC" standard mixed input
("AAABBC", "AABC") -> "AABBC" duplicate requirement
("a", "a") -> "a" minimum size
("a", "A") -> "" case-sensitive and impossible
("abc", "abcd") -> "" s is shorter than t
("abc", "") -> "" defensive empty target短いランダム文字列に対しては、全区間を列挙する 2 乗のオラクルと比較します。最適化された結果について 3 つの性質（s の連続部分文字列であること、その頻度が t を満たしていること、より短い区間で t を満たすものがないこと）を検証します。差分テストは、formed の過剰カウント、1 つズレの長さエラー（off-by-one）、誤った削除順序を発見するのに特に効果的です。
s が非常に小さく、単発の処理であり、パフォーマンス要件が緩い場合は、2 乗のバージョンのほうがコードが短く、面接のプレッシャー下では安全に記述できる場合もあります。しかし、長さの上限が 100000 で線形時間が明示的に求められている場合、スライディングウィンドウが適切な最終解となります。
模範解答例
「まず、包含判定が文字の出現頻度に基づいており、順序は問わず、大文字と小文字が区別されることを確認します。 素朴な手法では、各左端を固定して右に伸ばしていきますが、これは最悪ケースで 2 乗の計算量になります。この問題には有用な単調性があります。右に文字を追加しても有効なウィンドウが無効化されることはなく、一旦ウィンドウが有効になれば、左端を進めることでその右端で終わる最短の有効ウィンドウを見つけることができます。
t の頻度を need に、現在の対象頻度を window に格納します。また、要求数に達した文字種数である formed を管理します。文字を追加した際、そのカウントがちょうど要求数と等しくなったときにのみ formed を増やします。ウィンドウが有効である間は、左の文字を削除する前に解を記録します。削除前の時点でその文字がちょうど要求数である場合、削除によってその文字種は不足するため、formed を減らします。
重要な不変条件は、window が [left, right] 内の実際の出現数と一致すること、そして formed が条件を満たした対象文字種数と一致することです。内側ループは各右端に対するすべての有効な左端をチェックし、最短の有効ウィンドウを通り過ぎた直後に停止します。全体の最適解はこれらの候補の中に必ず存在します。両ポインタは右にのみ進むため、各位置の追加と削除は高々 1 回です。時間計算量は O(|s| + |t|)、空間計算量は O(u) です。重複を含むターゲット、解なし、1 文字の入力、大文字小文字の違い、および全探索オラクルと比較するランダムな短い文字列でテストします。」
よくある間違い
- 対象文字のセット（Set）のみを保持する → 重複の要求数が失われる → 要求頻度を記録する。
- 対象文字が追加されるたびに一致数をインクリメントする → 過剰な文字によって誤って有効と判定される → 要求数にちょうど達した最初の遷移でのみ
formedを増やす。 - 対象文字を削除する際に常に
formedをデクリメントする → 余剰分の削除であればウィンドウは有効なまま → 削除前のカウントが要求数と一致していた場合のみデクリメントする。 - 有効になった後に 1 回しか縮小しない → 同じ右端で終わるより短いウィンドウが見逃される → ウィンドウが初めて無効になるまで
whileループで縮小する。 - 解を記録する前に
leftを進める → 有効な最小ウィンドウがスキップされたり、長さが 1 つズレる → 先に[left, right]を計測する。 - ポインタを動かすたびに
need全体をスキャンする → 有効性チェックにuの係数がかかる → 達成文字種数をインクリメンタルに維持する。 - 部分列（subsequence）の問題として解いてしまう → 結果の内部で位置がスキップされ、連続部分文字列でなくなる → 各ウィンドウを 1 つの連続したインデックス区間として表現する。
- 対象外の文字を除外した後に、除外後のインデックスで元文字列をスライスする → フィルタ後の位置が元の位置と直接一致しない → ポインタは元文字列上に置き、マップ内でのみ対象外文字を無視する。
- 内側ループを 2 乗と誤認する → 左ポインタが全体として単調増加することを無視している → 各位置が高々 1 回しか除外されないことからならし計算量で評価する。
- 標準例しかテストしない → 重複、解なしケース、大文字小文字の区別が未検証のままになる → 意図的なコーナーケースとランダムオラクルを追加する。
フォローアップ質問と回答
フォローアップ 1：一致した文字の総数ではなく、達成された文字種数をカウントするのはなぜですか？
どちらの状態でも正しいアルゴリズムを構築できますが、文字種数をカウントするほうが閾値遷移が明示的になります。need[A] = 2 の場合、その文字種が満たされるのは window[A] が 1 から 2 に変化したときのみであり、3 つ目の A はその状態を変えません。削除時も、カウントが 2 から 1 になったときのみ状態が解除されます。総文字数カウンタを使用する場合は window[c] <= need[c] の間だけインクリメントし、対称的な削除ルールを適用する必要がありますが、記述ミスを起こしやすくなります。
フォローアップ 2：t に重複文字がない場合、何を簡略化できますか？
need のすべての値が 1 になるため、window は対象文字のカウント、または出現カウントと組み合わせたセットで表現できます。ただし、ウィンドウ内には同じ対象文字が複数現れる可能性があり、1 つ削除しても文字種としては満たされたままになることがあります。一般的な頻度ベースの実装を維持しても定数倍のオーバーヘッドはごくわずかであり、元の問題もそのまま処理できます。
フォローアップ 3：t で指定された順序で文字が出現しなければならない場合はどうなりますか？
それは Minimum Window Subsequence（最小ウィンドウ部分列）問題になります。頻度の網羅だけでは有効性を証明できなくなります。例えば s = "cba" は t = "abc" の頻度を満たしますが、順序が異なります。解法としては、一致した各プレフィックスの開始位置を保持する動的計画法や、候補となる端点の周囲を前後にスキャンする手法が考えられます。計算量は再分析が必要であり、formed === required を有効性判定条件として再利用することはできません。
フォローアップ 4：タイとなる最短ウィンドウをすべて返すにはどうすればよいですか？
一意性の保証がない場合でも、bestLength は従来通り保持します。より短いウィンドウが現れたら結果リストをクリアしてその区間を追加します。同じ長さのウィンドウが現れたら追加（append）します。別々の探索パスから同じテキスト区間が再検出される可能性がある場合は [left, right] で重複排除します。この 2 ポインタ走査は各区間を高々 1 回しか訪問しないため、ここでは追加の Set は不要です。
フォローアップ 5：s がメモリに収まらない文字ストリームの場合はどうしますか？
必要な頻度とポインタの状態はオンラインで更新できますが、元のテキストを返すには現在の候補区間を保持しておく必要があります。グローバルオフセットとともに left から最新位置までの文字をキューに格納できます。長い間有効なウィンドウが現れない場合、そのバッファはそれまでに読み込んだストリーム全体近くまで膨らむ可能性があります。長さとオフセットのみを返すのであれば対象文字の位置周辺をより圧縮できますが、テキスト自体を返すには最大ウィンドウサイズの設定や外部ストレージポリシーが明示的に必要になります。
フォローアップ 6：任意の Unicode テキストをサポートするにはどうすればよいですか？
まず照合の単位を定義します。Unicode コードポイントの場合は、コードポイント単位で反復処理を行い、元の JavaScript 文字列をスライスするために対応する UTF-16 コードユニットのオフセットを保持します。ユーザーが認識する 1 文字に複数のコードポイントが含まれる場合、書記素クラスタの一致には信頼性の高いセグメンタが必要です。また、正規化によって文字の一致判定が変わるため、元のテキストへのマッピングを維持しつつ、カウント前に一貫して正規化を適用する必要があります。
フォローアップ 7：ランダムテストのオラクルはどうやって信頼性を担保しますか？
オラクルは短い文字列でのみ実行するため、すべての [left, right] を列挙し、各区間を直接再カウントして、長さと開始位置で選択することができます。その制御フローは最適化アルゴリズムとは意図的に異なっており、低速ですが監査が容易です。まず固定例でオラクルを検証し、その後のランダム差分テストで結果の長さ、連続性、頻度カバー率を比較することで、共通のバグが混入する可能性を低減させます。