スライディングウィンドウで必要な文字を全部含む最短の部分を探す

スライディングウィンドウ問題 103

文字列 s の中で、t の文字を数まで全部含む、いちばん短い続いた部分を探します。足りない文字の数を 1 つの数で持ち、右へ伸ばして全部そろったら左を縮める、スライディングウィンドウの練習です。

海外で定番の問題リスト 4 本には入っていません

問題

文字列 s と t を受け取ります。s の続いた部分のうち、t の文字を全部、数まで含む物 (t に同じ文字が 2 つあれば、その文字を 2 つ以上含む物) で、いちばん短い物を返す関数を書いてください。

そういう部分が無ければ、空の文字列 "" を返します
いちばん短い物が 2 つ以上あるときは、s の中でいちばん左にある物を返します
英字の大文字と小文字は別の文字として扱います
部分の中に、t に無い文字や、余った文字が入っていてもかまいません
s と t の長さは、どちらも 1 以上 100000 以下で、英字の大文字と小文字だけでできています

入力と出力の例

例 1

A、B、C を全部含む部分のうち、最後の 3 文字の "ACB" がいちばん短くなります。

s = "CXAYBZACB" t = "ABC"

"ACB"

例 2

t には N が 2 つあります。N を 2 つと A を 1 つ含む部分で最も短いのは、左から 3 文字目からの "NAN" です。

s = "BANANA" t = "ANN"

"NAN"

例 3

s の B は大文字で、t の b は小文字です。別の文字なので、含む部分はありません。

s = "aBc" t = "b"

面接での聞かれ方

面接では、難しい問いの代表として出されることがあります。

「t の文字を全部含む、s の最小の窓を求めてください」
「t に同じ文字が何個もあるときは、その数だけ要りますか？」と、範囲を自分から確かめるかを見られます
「同じ長さが 2 つあったら、どちらを返しますか？」も、聞いておくと答えが 1 つに決まります

全部の部分を調べる書き方を先に口に出し、そこから「伸ばす、縮める」の窓に移ると、考えの筋が伝わります。

ヒント

まだ開いていません

付箋は 4 枚。下の段ほど答えに近づきます

ヒント 2
ヒント 3
ヒント 4答えに近い

アルゴリズムのチートシートの「配列と文字列」に、この型の要点を表とコードでまとめています。

配列と文字列の問題は、全部の組を調べると手間が大きくなる所を、窓や左右の添字で減らす形が多いです。

まず考える手順

段 1

素直に書くなら、始まりを決め、終わりを右へ伸ばしながら文字を数え、t の文字が全部そろった所で長さを比べます。始まりが n 通り、伸ばすのも最大 n 回なので、O(n²) 回の確かめになります。長さ 10 万では遅すぎます。

段 2

窓を使います。右の端を伸ばしていき、t の文字が全部そろったら、そろったままでいられる限り左の端を縮めます。縮められなくなった所が、いまの右の端で終わる最短の部分です。そこで長さを比べ、もう 1 つ縮めて足りない状態に戻し、また右を伸ばします。左右の端は前へ進むだけです。

段 3

「全部そろったか」を毎回 t の文字の種類ぶん比べると手間がかかります。そこで、文字ごとに「あと何個要るか」を表 need に持ち、足りない文字の合計を 1 つの数 missing で持ちます。右に入った文字がまだ要る文字なら missing を 1 減らし、左から出た文字で要る数が 0 から 1 に戻ったら missing を 1 増やします。missing が 0 なら全部そろっています。

段 4

t に無い文字も表に入れて、要る数を負にしてかまいません。負の数は「余っている」という意味で、左から出ても 0 より大きくならないので、missing は動きません。いちばん左の物を返す決まりは、長さが真に短いときだけ書き換えれば守れます。右の端の順に見つけるので、同じ長さなら先に見つけた方が左にあります。

解答

Python

from collections import Counter


def min_cover(s, t):
    need = Counter(t)
    missing = len(t)
    lo = 0
    start = 0
    best_len = len(s) + 1
    for r, c in enumerate(s):
        if need[c] > 0:
            missing -= 1
        need[c] -= 1
        while missing == 0:
            size = r - lo + 1
            if size < best_len:
                best_len = size
                start = lo
            out = s[lo]
            need[out] += 1
            if need[out] > 0:
                missing += 1
            lo += 1
    if best_len > len(s):
        return ""
    end = start + best_len
    return s[start:end]

JavaScript

function minCover(
  s,
  t
) {
  const need = {};
  for (const c of t) {
    need[c] ??= 0;
    need[c]++;
  }
  const n = s.length;
  let missing = t.length;
  let lo = 0;
  let start = 0;
  let bestLen = n + 1;
  for (let r = 0; r < n; r++) {
    const c = s[r];
    need[c] ??= 0;
    if (need[c] > 0) missing--;
    need[c]--;
    while (missing === 0) {
      const size = r - lo + 1;
      if (size < bestLen) {
        bestLen = size;
        start = lo;
      }
      const out = s[lo];
      need[out]++;
      if (need[out] > 0) {
        missing++;
      }
      lo++;
    }
  }
  if (bestLen > n) return "";
  const end = start + bestLen;
  return s.slice(start, end);
}

Go

func minCover(
	s string,
	t string,
) string {
	need := map[byte]int{}
	for i := 0; i < len(t); i++ {
		need[t[i]]++
	}
	missing := len(t)
	lo, start := 0, 0
	bestLen := len(s) + 1
	for r := 0; r < len(s); r++ {
		c := s[r]
		if need[c] > 0 {
			missing--
		}
		need[c]--
		for missing == 0 {
			size := r - lo + 1
			if size < bestLen {
				bestLen = size
				start = lo
			}
			out := s[lo]
			need[out]++
			if need[out] > 0 {
				missing++
			}
			lo++
		}
	}
	if bestLen > len(s) {
		return ""
	}
	end := start + bestLen
	return s[start:end]
}

need[c] は「文字 c があと何個要るか」で、負なら余っている数です。missing は足りない文字の合計で、0 のあいだは左の端を縮め続けます。縮めて足りなくなった所で繰り返しを抜けるので、抜けたときの窓は 1 文字足りない状態です。best_len (bestLen) を s より 1 長い値から始め、最後まで書き換わらなければ、そろう部分が無かったと分かります。

計算量

時間は O(n + m) です。n は s の長さ、m は t の長さです。右の端も左の端も、それぞれ前へ n 回までしか進みません
使う記憶は O(k) です。k は文字の種類の数で、英字なら 52 種類までなので O(1) と言ってもかまいません
段 1 の全部の部分を調べる書き方は、O(n²) 回の確かめになります

よくある間違い

文字の種類だけを数え、数を数えない。例 2 で N を 1 つ含めばよいと考えると、"AN" を返します。t の同じ文字は、その数だけ要ります
missing を、要らない文字が入ったときにも減らす。 need[c] > 0 のときだけ減らします。余った文字や t に無い文字で減らすと、そろっていないのにそろったと見ます
縮めるのを if で 1 回だけにする。 1 回では最短まで縮まらず、例 1 では "ACB" を見落として "CXAYB" を返します。そろっているあいだは縮め続けます
同じ長さで答えを書き換える。 <= で比べると、同じ長さのとき右の物に替わり、いちばん左を返す決まりを破ります
大文字と小文字を同じに見る。例 3 で "B" を返してしまいます。決まりを最初に確かめます

解答を動かした版 Python 3.14.7Node.js 24.22.1Go 1.24.2確認日 2026年11月8日

main.py

def min_cover(s: str, t: str) -> str:
    """
    Goal: 何を返すか

    idea1: まず思いつく案
    -> runtime: O(?)  space: O(?)

    idea2: もっと速い案
    -> runtime: O(?)  space: O(?)

    edge case: 空、1 つだけ、など
    """
    # ここに書きます
    pass


# 「実行」を押すと、この行の結果が出ます
print(min_cover("CXAYBZACB", "ABC"))

できているか「例で確かめる」を押すと、問題の例を全部この関数に渡して、通ったかをここに出します