C++で解く「すべての単語を連結した部分文字列」問題 ― ハッシュマップとスライディングウィンドウによる解法

問題概要

文字列 s と、すべて同じ長さの単語からなる配列 words が与えられます。このとき、s の中に存在する「words の各単語を、間に他の文字を挟まずにちょうど1回ずつ連結した部分文字列」の開始インデックスをすべて求めるのが目的です。

たとえば、入力が "barfoothefoobarman"、words が ["foo", "bar"] である場合、出力は [0, 9] になります。インデックス 0 から始まる部分文字列は "barfoo"、インデックス 9 から始まる部分文字列は "foobar" であり、どちらも "foo" と "bar" を1回ずつ連結したものに一致するためです。

解法のアプローチ

この問題は、ハッシュマップ（unordered_map）による単語の出現回数の管理と、スライディングウィンドウ（固定長の窓を少しずつずらしながら走査する手法）を組み合わせることで効率的に解けます。全体の流れは次のとおりです。

ok() メソッド：部分文字列が条件を満たすかを判定する

1. 引数として文字列 s、マップ wordCnt、単語の長さ n を受け取ります。
2. s の先頭 n 文字を temp にコピーします。
3. i を n から s のサイズ − 1 までループします。
   • temp のサイズが n の倍数のとき、temp が wordCnt に存在しなければ false を返します。
   • 存在する場合は、wordCnt[temp] が 1 なら wordCnt から temp を削除し、そうでなければ wordCnt[temp] を 1 減らします。いずれの場合も temp を空文字列に戻します。
   • その後、temp に s[i] を追加します。
4. ループ終了後、残った temp に対しても同じチェックを行います。
5. 最後に wordCnt が空になっていれば true を返します。これは、すべての単語を過不足なく使い切ったことを意味します。

findSubstring() メソッド：メインの処理

1. a または b のサイズが 0 の場合、空の配列を返します。
2. マップ wordCnt を作成し、b に含まれる各単語の出現回数を記録します。
3. 結果を格納する配列 ans を用意します。
4. window ＝ 単語の個数 × 1単語あたりの文字数 として、窓のサイズを決めます。
5. 文字列 a の先頭 window 文字を temp にコピーします。
6. i を window から a のサイズ − 1 までループします。
   • temp のサイズが window の倍数で、ok(temp, wordCnt, b[0].size()) が true を返すなら、開始位置 i − window を ans に追加します。
   • temp に a[i] を追加し、サイズが window を超えたら先頭の 1 文字を削除します。これにより窓が 1 文字ずつ右へスライドしていきます。
7. ループ終了後も同様に判定を行い、条件を満たす場合は a のサイズ − window を ans に追加します。
8. ans を返します。

C++ 実装例

以下の実装を見ると、処理の流れがより明確になります。

#include <bits/stdc++.h>
using namespace std;
void print_vector(vector<auto> v){
    cout << "[";
    for(int i = 0; i<v.size(); i++){
       cout << v[i] << ", ";
    }
    cout << "]"<<endl;
}
class Solution {
public:
    bool ok(string s, unordered_map <string, int> wordCnt, int n){
       string temp = "";
       for(int i = 0; i < n; i++){
          temp += s[i];
       }
       for(int i = n; i < s.size(); i++){
          if(temp.size() % n == 0){
             if(wordCnt.find(temp) == wordCnt.end())return false;
             else{
                if(wordCnt[temp] == 1){
                   wordCnt.erase(temp);
                   temp = "";
                }
                else{
                   wordCnt[temp]--;
                   temp = "";
                }
             }
          }
          temp += s[i];
       }
       if(wordCnt.find(temp) == wordCnt.end())return false;
       else{
          if(wordCnt[temp] == 1){
             wordCnt.erase(temp);
             temp = "";
          }
          else{
             wordCnt[temp]--;
             temp = "";
          }
       }
       return wordCnt.size() == 0;
    }
    vector<int> findSubstring(string a, vector<string> &b) {
       if(a.size() == 0 || b.size() == 0)return {};
       unordered_map <string, int> wordCnt;
       for(int i = 0; i < b.size(); i++)wordCnt[b[i]]++;
       vector <int> ans;
       int window = b.size() * b[0].size();
       string temp ="";
       for(int i = 0; i < window; i++)temp += a[i];
       for(int i = window; i < a.size(); i++){
          if(temp.size() % window == 0 && ok(temp, wordCnt, b[0].size())){
             ans.push_back(i - window);
          }
          temp += a[i];
          if(temp.size() > window)temp.erase(0, 1);
       }
       if(temp .size() % window ==0 && ok(temp, wordCnt, b[0].size()))ans.push_back(a.size() - window);
       return ans;
    }
};
main(){
    vector<string> v = {"foo", "bar"};
    Solution ob;
    print_vector(ob.findSubstring("barfoothefoobarman", v));
}

入力例

s = "barfoothefoobarman"
words = ["foo", "bar"]

出力例

[0, 9]

まとめ

本手法では、各開始位置ごとに窓内の文字列を単語長ごとに区切り、ハッシュマップと照合することで、words の各単語をちょうど1回ずつ使う部分文字列を正確に検出できます。単語の並び順は問われないため、「出現回数を記録し、照合のたびに消費していく」というマップ操作がポイントになります。スライディングウィンドウにより候補位置を順に走査することで、無駄な再計算を避けながらすべての該当インデックスを効率よく収集できる点も大きな特徴です。