長さを決めた窓で並べ替えた言葉が文の中に続けて入っているか調べる

言葉 p の文字を並べ替えた物が、文 s の中に途切れずに入っているかを調べます。p と同じ長さの窓を 1 文字ずつずらし、窓の中の文字の数を足し引きして比べる、長さを決めたスライディングウィンドウの練習です。

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

問題

英小文字だけの言葉 p と、英小文字だけの文 s を受け取ります。p の文字を並べ替えてできる言葉 (並べ替えないそのままも含む) のどれかが、s の中に途切れずに入っていれば true、入っていなければ false を返す関数を書いてください。

並べ替えでは、文字の種類と数をそのまま使います。同じ文字が 2 つあれば、2 つとも使います
s の中で飛び飛びに拾った文字は数えません。続いた部分だけを見ます
p と s の長さは、どちらも 1 以上 10000 以下です。p が s より長いこともあります

入力と出力の例

例 1

s の左から 4 文字目からの "eat" は、"tea" の文字を並べ替えた言葉です。

p = "tea" s = "greateagle"

true

例 2

s に a も b もありますが、あいだに x がはさまっていて、続いた 2 文字の a と b がありません。

p = "ab" s = "axb"

false

例 3

a が 2 つの言葉です。s の "baa" は、a が 2 つと b が 1 つで、数まで合っています。

p = "aab" s = "xbaay"

true

面接での聞かれ方

面接では、アナグラムや並べ替えの言葉で渡されることがよくあります。

「s が、p の並べ替えのどれかを部分文字列として含むか判定してください」
「文字は英小文字だけですか？」と、自分から確かめるかを見られます
書き終えたあとに「1 回ずらすたびに 26 文字を比べずに済みませんか？」と広げられることもあります

並べ替えを全部作ると、長さ 10 の言葉でも 360 万通りを超えます。並べ替えを作らずに「文字の種類と数が同じか」で比べる、と気づくのが入口です。

ヒント

まだ開いていません

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

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

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

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

まず考える手順

段 1

2 つの言葉が並べ替えの関係にあるのは、文字ごとの数が全部同じときです。順は関係ありません。そこで、s の中の、p と同じ長さの続いた部分を全部見て、文字の数が p と同じ物があるかを調べれば答えが出ます。

段 2

素直に書くなら、始まりの位置ごとに長さ m (p の長さ) の部分を切り出して数え直します。1 か所に O(m) かかるので、全体で O(n × m) です。両方が 1 万なら 1 億回ほどになります。

段 3

隣り合った 2 つの部分は、左端の 1 文字が抜けて、右に 1 文字が入っただけの違いです。そこで、長さ m の窓を 1 文字ずつ右へずらし、入った文字の数を 1 足し、抜けた文字の数を 1 引きます。数え直さずに、いまの窓の文字の数が分かります。

段 4

窓の文字の数と p の文字の数を、英小文字の 26 個ぶんの表で比べます。比べるのは 1 回に 26 個で、言葉の長さに関わらず一定です。p が s より長ければ、窓が作れないので、最初に false を返します。

解答

Python

from collections import Counter


def has_shuffled(p, s):
    m = len(p)
    if m > len(s):
        return False
    ref = Counter(p)
    win = Counter(s[:m])
    if win == ref:
        return True
    for i in range(m, len(s)):
        win[s[i]] += 1
        win[s[i - m]] -= 1
        if win == ref:
            return True
    return False

JavaScript

function hasShuffled(
  p,
  s
) {
  const m = p.length;
  const n = s.length;
  if (m > n) return false;
  const ref = Array(26).fill(0);
  const win = Array(26).fill(0);
  const idx = (c) =>
    c.charCodeAt(0) - 97;
  for (let i = 0; i < m; i++) {
    ref[idx(p[i])]++;
    win[idx(s[i])]++;
  }
  const same = () => win.every(
    (v, j) => v === ref[j]
  );
  if (same()) return true;
  for (let i = m; i < n; i++) {
    win[idx(s[i])]++;
    win[idx(s[i - m])]--;
    if (same()) return true;
  }
  return false;
}

Go

func hasShuffled(
	p string,
	s string,
) bool {
	m := len(p)
	if m > len(s) {
		return false
	}
	var ref, win [26]int
	for i := 0; i < m; i++ {
		ref[p[i]-'a']++
		win[s[i]-'a']++
	}
	if win == ref {
		return true
	}
	for i := m; i < len(s); i++ {
		win[s[i]-'a']++
		win[s[i-m]-'a']--
		if win == ref {
			return true
		}
	}
	return false
}

ref が p の文字の数、win がいまの窓の文字の数です。最初に s の先頭 m 文字で窓を作って比べ、そのあとは右に入る s[i] を足し、左から出ていく s[i - m] を引きます。窓はいつも長さ m です。JavaScript と Go の 97 と 'a' は、引くと a が 0、z が 25 になる文字の番号です。Python の Counter と Go の長さの決まった配列は、== でそのまま比べられます。Python の Counter は、数が 0 になった文字を無い文字と同じに見て比べます。

計算量

時間は O(26 × n + m) です。窓を n 回ずらし、1 回に 26 個を比べます。文字の種類が決まっているので、O(n + m) と言ってもかまいません
使う記憶は O(1) です。26 個の表を 2 つ持つだけです
段 2 の数え直す書き方は O(n × m)、並べ替えを全部作る書き方は m の階乗に比例し、とても間に合いません

よくある間違い

p の並べ替えを全部作ってから探す。 長さ 10 で 360 万通りを超え、すぐ間に合わなくなります。文字の数で比べます
文字の種類だけを比べて、数を比べない。例 3 の "aab" は a が 2 つです。種類だけなら、a が 1 つで b が 2 つの "abb" のような窓でも合ってしまいます
窓から出ていく文字を引き忘れる。窓が伸び続け、例 2 のように文字が飛び飛びにある s でも true を返します
p が s より長いかを確かめずに、最初の窓を作る。 s の先頭 m 文字を読むところで、Go は範囲の外を読んで止まり、JavaScript も無い文字を読んでエラーになります。最初に false を返します

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

main.py

def has_shuffled(p: str, s: str) -> bool:
    """
    Goal: 何を返すか

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

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

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


# 「実行」を押すと、この行の結果が出ます
print(has_shuffled("tea", "greateagle"))

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