Permutation in String
文字列の順列とは、元の文字列と同じ文字を同じ回数ずつ使い、順序を変えたものです。tar、rat、artは互いに順列です。小文字の英字で構成された2つの文字列s1とs2が与えられます。s1の順列のいずれかが部分文字列（連続する文字の並び）としてs2に現れる場合はtrueを、そうでない場合はfalseを返してください。
関数
- s1string
- 並べ替える文字
- s2string
- 検索対象となる文字列
- 戻り値boolean
- s2 の部分文字列が s1 の並べ替えである場合は true
制約
1 ≤ s1.length ≤ 2 × 1041 ≤ s2.length ≤ 5 × 104s1とs2には、小文字の英字（aからz）のみが含まれます。s1はs2より長い場合があります。
例
- 入力
- s1 = "tar"s2 = "smartphone"
- 出力
- true
- 説明
smartphoneのインデックス2から4までの部分文字列artには、tarと同じ文字であるaが1つ、rが1つ、tが1つ含まれています。
- 入力
- s1 = "noon"s2 = "onion"
- 出力
- false
- 説明
- 長さ4の部分文字列は
onioとnionです。noonにはnが2つ、oが2つ必要ですが、各ウィンドウにはそのどちらかの代わりにiが含まれています。noonの各文字はonionに含まれていますが、正しい個数を含むウィンドウはありません。
- 入力
- s1 = "abcd"s2 = "dcb"
- 出力
- false
- 説明
abcdのどの順列も4文字ですが、dcbは3文字しかないため、その中に含まれることはありません。
提出時に隠しテスト+17件
発展問題
引き続きO(m + n)時間で、s1の順列が始まるs2内のすべてのインデックスを返せますか？
ヒント
1つずつ開いてください。開くたびに少しずつ答えに近づきます。
順列では、文字の順序は重要ではありません。
s2の部分文字列について、それがs1の順列であるかどうかを決める要素は何でしょうか。また、その長さはどれくらいでなければならないでしょうか？長さが
m = s1.lengthの部分文字列だけが条件を満たし、その部分文字列がs1の順列となるのは、26種類の文字の出現回数がs1の出現回数と一致するときに限ります。長さ
mのウィンドウをs2上でスライドさせます。各ステップで右側に1文字追加し、左側の1文字を削除するので、数え直す代わりにウィンドウ内のカウントを1つ増やして1つ減らし、s1のカウントと比較します。
解説
s1の順列を列挙するのは現実的ではありません。10文字だけでも、並べ方は3,628,800通りあります。この問題を解決するには、順序を気にしないようにします。s2の部分文字列がs1の順列であるのは、その長さがmと同じで、各文字の個数もすべて一致するときです。したがって、候補はすべて同じ固定長のウィンドウになります。s2上でウィンドウを1つずつスライドさせ、各ステップで1文字を加え、1文字を取り除いて、文字の個数を更新できます。
ウィンドウを毎回最初から数える
正しいが、最大のテストでは終わらない
考え方
s1 のすべての順列を作って探すという素直な方法は、すぐに行き詰まります。20文字では、2 × 10^18 を超える並び方があるからです。代わりに、問いの立て方を変えましょう。s2 の部分文字列が s1 の順列となるのは、文字数がちょうど m で、各文字を s1 と同じ回数だけ使っている場合です。部分文字列内での順序は関係ありません。
そこで、まず s1 の各文字を、26個の数値からなる表で一度だけ数えます。インデックスは a が0、z が25です。次に、s2 の長さ m の部分文字列をすべて取り出し、その文字を新しい表で数えて、2つの表を比較します。smartphone の中で tar を探す場合、ウィンドウは sma、mar、art のようになり、art が一致します。a、r、t がそれぞれ1つずつ含まれているからです。
この方法が正しいのは、候補をすべて調べるからです。一方、隣り合うウィンドウは m-1 文字を共有しているのに、そのすべてを数え直すため、処理が遅くなります。m = 15,000、n = 50,000 の場合、長さ15,000文字のウィンドウが35,001個あり、処理回数は約5 × 10^8になります。
アルゴリズム
s1がs2より長い場合は、falseを返します。- 26個のゼロが入った表
needで、s1の各文字の数を数えます。 - 0から
n-mまでの各開始インデックスについて、その位置からのm文字の数を新しい表で数えます。 - その表が
needと等しければ、trueを返します。 - 最後のウィンドウの後、
falseを返します。
def checkInclusion(s1, s2):
m, n = len(s1), len(s2)
if m > n:
return False
need = [0] * 26 # need[0] is 'a', need[25] is 'z'
for ch in s1:
need[ord(ch) - 97] += 1
for start in range(n - m + 1):
# Count the letters of s2[start : start + m] from scratch
window = [0] * 26
for i in range(start, start + m):
window[ord(s2[i]) - 97] += 1
if window == need:
return True
return Falseウィンドウをスライドさせて、26個のカウントを比較する
考え方
隣り合う2つのウィンドウは、2文字しか異なりません。marからartに移ると、左側のmを削除し、右側にtを追加します。そこで、m文字を数え直す代わりに、現在のウィンドウ用のテーブルを1つ保持し、各ステップで+1と-1の更新を1回ずつ行います。
s1からneedを、s2の先頭のm文字からwindowを作り、両者を比較します。次に、mからn-1までの各iについて、s2[i]を追加し、s2[i-m]を削除して、もう一度比較します。このときウィンドウはs2[i-m+1..i]となり、引き続き長さはm文字です。
各ステップのコストは、mの値にかかわらず、2回の更新と26個の数値の比較です。最大の入力では、約26 × 50,000 = 1.3 × 10^6回の操作となり、s2の長さに対して線形です。これは、ほとんどの面接官が期待する解法です。
アルゴリズム
s1がs2より長い場合は、falseを返します。s1の文字をneedに、s2の最初のm文字をwindowに数えます。- 2つのテーブルが等しい場合は、
trueを返します。 mからn-1までの各iについて、s2[i]の分を1加算し、s2[i-m]の分を1減算します。テーブルが等しい場合はtrueを返します。falseを返します。
def checkInclusion(s1, s2):
m, n = len(s1), len(s2)
if m > n:
return False
need = [0] * 26
window = [0] * 26
for i in range(m):
need[ord(s1[i]) - 97] += 1
window[ord(s2[i]) - 97] += 1 # the first window is s2[0 : m]
if window == need:
return True
for i in range(m, n):
window[ord(s2[i]) - 97] += 1 # s2[i] enters on the right
window[ord(s2[i - m]) - 97] -= 1 # s2[i - m] leaves on the left
if window == need:
return True
return Falseウィンドウをスライドさせて、バランスの取れていない文字を追跡する
考え方
各ステップで26個の数を比較すると、ステップごとに変わるのは2つだけなのに、同じ作業を繰り返すことになります。代わりに、1つの表 balance を使います。balance[c] は、s1 に含まれる文字 c の個数から、ウィンドウ内の個数を引いた値です。すべての26個の残高が0である場合に限り、ウィンドウは s1 の順列です。表とあわせて、残高が0ではない文字の数 unbalanced も保持し、0になった瞬間に true と答えます。
記録の更新には1つルールがあります。balance[c] を変更する前に、その値が0なら、その文字は残高が一致しなくなるので、unbalanced に1を加えます。変更後に値が0なら、その文字の残高が一致したので、1を引きます。文字がウィンドウに入ると残高は1減り、出ると1増えます。残高が2から1に変わっても、どちらの確認も行いません。それで正しいのです。文字の残高はもともと一致しておらず、今も一致していないからです。
tar と smartphone を順に見ていきましょう。最初の残高は a: 1、r: 1、t: 1 なので、unbalanced は3です。s と m が入り、値は5になります。次に a が入り、aの残高が0になるため、値は4になります。r が入ると（3）、s が出ます（2）。t が入ると（1）、m が出て（0）、ウィンドウ内の art が答えです。
最初の文字から unbalanced == 0 を確認できます。ウィンドウ内の文字数が m 未満の間は、残高の合計が正の値になるため、少なくとも1つは0ではありません。各ステップの処理量は一定なので、スキャン全体の計算量は O(m + n) です。また、表には常に26個の数が入るため、空間計算量は O(1) です。
アルゴリズム
s1がs2より長い場合は、falseを返します。s1の文字数をbalanceに数え、バランスが0以外の文字の数をunbalancedに設定します。s2の各インデックスiについて、s2[i]のバランスから1を引きます。そのバランスが0だった場合はunbalancedに1を加え、0になった場合は1を引きます。i ≥ mの場合、同じ方法でs2[i-m]のバランスに1を加えます。unbalancedが0の場合は、trueを返します。ループの後、falseを返します。
def checkInclusion(s1, s2):
m, n = len(s1), len(s2)
if m > n:
return False
# balance[c]: copies of letter c in s1 minus copies in the window
balance = [0] * 26
for ch in s1:
balance[ord(ch) - 97] += 1
unbalanced = sum(1 for b in balance if b != 0)
for i in range(n):
# s2[i] enters the window on the right
c = ord(s2[i]) - 97
if balance[c] == 0:
unbalanced += 1
balance[c] -= 1
if balance[c] == 0:
unbalanced -= 1
# s2[i - m] leaves on the left once the window would pass m letters
if i >= m:
c = ord(s2[i - m]) - 97
if balance[c] == 0:
unbalanced += 1
balance[c] += 1
if balance[c] == 0:
unbalanced -= 1
if unbalanced == 0:
return True
return False
落とし穴と境界ケース
誤答の多くは、ウィンドウの端の処理や、文字の出現回数ではなく、どの文字が含まれているかを確認することが原因です。
s1のすべての文字がウィンドウ内にあることだけを確認する。onioにはnoonのすべての文字が含まれていますが、noonの順列ではありません。出現回数を比較しましょう。- 削除する文字を間違える。
s2[i]が入るとき、ウィンドウから出る文字はs2[i-m]なので、ウィンドウはs2[i-m+1..i]になります。s2[i-m+1]を削除すると、ウィンドウに残る文字はm-1個です。 - 最初のウィンドウを見落とす。スライドした後にしか比較しないと、インデックス0にある順列は見つかりません。
s1のほうがs2より長い場合を忘れる。Rustでは、符号なしの長さに対するn - mはアンダーフローし、Swiftでは範囲0...(n - m)によってクラッシュします。まずfalseを返しましょう。==が参照を比較する言語で、配列を==で比較する。JavaScriptとDartでは、異なる2つの配列が==になることはありません。JavaではArrays.equalsを使いましょう。
よくある質問4
Permutation in String の時間計算量はどれくらいですか？
スライディングウィンドウを使うと、O(m + n) です。ここで m は s1 の長さ、n は s2 の長さです。s1 を一度カウントし、その後 s2 の各文字がウィンドウに一度入り、一度出ます。各ウィンドウを毎回最初から数え直すと、代わりに O(n · m) のコストがかかります。
文字列内の順列を見つけることは、文字列内のアナグラムを見つけることと同じですか？
はい。s1の順列はそのアナグラムなので、s2内の長さmの部分文字列のいずれかがs1のアナグラムであるかどうかが問題です。2つの文字列全体のアナグラム判定では文字数を一度比較しますが、ここでは同じ比較をs2に沿ってスライドするウィンドウに対して行います。
ここでスライディングウィンドウのサイズが固定なのはなぜですか？
s1 のすべての順列はちょうど m 文字なので、一致する可能性があるのは長さ m のウィンドウだけです。重複のない最長部分文字列のような問題ではウィンドウを広げたり縮めたりしますが、ここでは両端が一緒に、一度に 1 ステップずつ移動します。
26個のカウンターの配列の代わりにハッシュマップを使えますか？
はい。文字列にあらゆる文字が含まれる可能性がある場合は、マップが必要です。小文字のみの場合は、要素数26の配列のほうが高速で、一定の領域しか使いません。マップを使う場合は、カウントが0になったらキーを削除して、同じ文字を持つ2つのマップが等しいと判定されるようにします。または、前の方法で使ったunbalancedカウンターを使うこともできます。マップでも同じように機能します。
Python
def checkInclusion(s1, s2):
# ここにコードを書いてくださいケース1
ケース2
ケース3
入力
s1 = "tar" s2 = "smartphone"
期待値
true