C++で文字列が長さKのすべてのバイナリコードを含むかどうかを判定する方法

二進文字列 s と整数 k が与えられたとき、長さ k のすべてのバイナリコード（合計 2^k 個）が s の部分文字列として含まれているかどうかを判定します。すべて含まれていれば true を、1つでも欠けていれば false を返します。

問題の例

たとえば、入力が S = "00110110"、k = 2 の場合、出力は true になります。長さ 2 のバイナリコードは「00」「01」「10」「11」の 4 種類あり、それぞれインデックス 0、1、3、2 の位置に存在するためです。

解法のアプローチ

この問題は、スライディングウィンドウの考え方とハッシュセットを組み合わせることで効率的に解くことができます。手順は以下の通りです。

• 重複しない部分文字列を記録するためのセット v を定義します。
• 一時的な文字列 temp を空文字列で初期化します。
• 必要なコードの総数 req = 2^k を計算します。
• i = 0 から s の末尾まで以下を繰り返します。
  • temp の末尾に s[i] を追加します。
  • i >= k のとき、temp の先頭の 1 文字を削除し、ウィンドウの長さを k に保ちます。
  • i >= k - 1 のとき、長さ k の部分文字列 temp をセット v に挿入します。
  • セット v のサイズが req に達した時点で、すべてのコードが見つかったことになるので true を返します。
• ループが終了しても条件を満たさなければ、false を返します。

この方法では、必要な種類数に達した時点で早期に処理を打ち切れるため、無駄な走査を避けられます。時間計算量は各ステップで長さ k の文字列操作が発生するため O(n・k)、空間計算量は O(2^k・k) となります。なお、部分文字列をビット値（整数）に変換して管理すれば、計算量を O(n) まで抑えることも可能です。

実装例

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

#include <bits/stdc++.h>
using namespace std;
typedef long long int lli;
class Solution {
public:
   lli fastPow(lli b, lli p){
      lli ret = 1;
      while (p) {
         if (p & 1) {
            ret *= b;
         }
         b *= b;
         p >>= 1;
      }
      return ret;
   }
   bool hasAllCodes(string s, int k) {
      unordered_set<string> v;
      string temp = "";
      lli req = fastPow(2, k);
      for (lli i = 0; i < s.size(); i++) {
         temp += s[i];
         if (i >= k) {
            temp.erase(0, 1);
         }
         if (i >= k - 1) {
            v.insert(temp);
         }
         if ((lli)v.size() == req)
            return true;
      }
      return false;
   }
};
main(){
   Solution ob;
   cout << (ob.hasAllCodes("00110110",2));
}

入力

"00110110",2

出力

1

出力が 1（true）となり、文字列「00110110」が長さ 2 のすべてのバイナリコードを含んでいることが確認できました。