C++で文字列の順列（並べ替え）を判定する方法

2つの文字列 s1 と s2 が与えられたとき、s2 の中に s1 の順列（アナグラム）が部分文字列として含まれていれば true を返す関数を作成する問題を考えてみましょう。つまり、「最初の文字列の順列のいずれかが、2番目の文字列の部分文字列になっているか」を判定します。

例えば、s1 = "abc"、s2 = "findcab" の場合、結果は true になります。なぜなら "abc" の順列である "cab" が s2 の中に存在するからです。

解決のためのアルゴリズム

この問題は「スライディングウィンドウ」と「文字の出現回数カウント」を組み合わせることで効率的に解けます。手順は以下の通りです。

• サイズ26の2つのベクトル cnt1 と cnt2 を作成する（それぞれ s1 と現在のウィンドウ内の各文字の出現回数を記録）
• i を 0 から s1 の長さまで繰り返し、cnt1[s1[i] - 'a'] の値を1ずつ増やす
• j := 0 とし、required := s1 の長さとする
• i を 0 から s2 の長さまで繰り返す
  • x := s2[i] とする
  • cnt2[x - 'a'] を1増やす
  • cnt1[x - 'a'] が0より大きく、かつ cnt2[x - 'a'] <= cnt1[x - 'a'] であれば、required を1減らす
  • j <= i かつ cnt2[s2[j] - 'a'] - 1 >= cnt1[s2[j] - 'a'] の間、次を繰り返す
    • cnt2[s2[j] - 'a'] を1減らす
    • j を1増やす
  • i - j + 1 が s1 の長さと等しく、required が 0 であれば true を返す
• ループが終了したら false を返す

C++による実装例

理解を深めるために、以下の実装を見てみましょう。

#include <bits/stdc++.h>
using namespace std;
class Solution {
public:
   bool checkInclusion(string s1, string s2) {
      vector <int> cnt1(26), cnt2(26);
      for(int i = 0; i < s1.size(); i++)cnt1[s1[i] - 'a']++;
      int j = 0;
      int required = s1.size();
      for(int i = 0; i < s2.size(); i++){
         char x = s2[i];
         cnt2[x - 'a']++;
         if(cnt1[x - 'a'] && cnt2[x - 'a'] <= cnt1[x - 'a']) required--;
         while(j <= i && cnt2[s2[j] - 'a'] - 1 >= cnt1[s2[j] - 'a']){
            cnt2[s2[j] - 'a']--;
            j++;
         }
         if(i - j + 1 == s1.size() && required == 0){
            return true;
         }
      }
      return false;
   }
};
main(){
   Solution ob;
   cout << (ob.checkInclusion("abc", "findcab"));
}

入力

"abc"
"findcab"

出力

1

アルゴリズムのポイント

この実装では、s2 を左から右へ走査しながら、長さが s1 と同じウィンドウを維持します。変数 required は「まだ揃っていない必要な文字の数」を表しており、これが 0 になり、かつウィンドウの幅が s1 の長さと一致した時点で、順列が見つかったことになります。ウィンドウの左端 j を動かしながら余分な文字を除去することで、全体の計算量は O(n) に抑えられます。