C++で0と1の個数が等しいバイナリ部分文字列を数える方法

問題概要

文字列 s が与えられたとき、「0 の個数と 1 の個数が等しく、かつすべての 0 とすべての 1 がそれぞれ連続してまとまっている」ような部分文字列の総数を求めます。同じ内容の部分文字列が複数回現れる場合は、出現した回数だけカウントします。

例えば、入力が "11001100" の場合、条件を満たす部分文字列は "1100"、"10"、"0011"、"01"、"1100"、"10" の 6 つとなるため、出力は 6 になります。

解法の考え方

この問題は、文字列を一度走査するだけで O(n) の計算量で解くことができます。ポイントは「現在の文字が連続している回数」と「直前まで別の文字が連続していた回数」を比較するというシンプルな発想です。

具体的には、以下の手順で処理を進めます。

• サイズ 2 の配列 cnt を定義し、0 で初期化します(cnt[0] は '0' の連続数、cnt[1] は '1' の連続数を管理)
• 答えを格納する変数 res を 0 で初期化します
• i を 0 から文字列の長さ未満まで 1 ずつ増やしながら、以下を繰り返します
  • num = s[i] - '0' として、現在の文字を数値に変換します
  • i が 0 のとき、または s[i] が直前の文字 s[i-1] と異なるとき(文字のグループが切り替わったとき)、cnt[num] を 0 にリセットします
  • cnt[num] を 1 増やします
  • cnt[num] が反対側の文字の連続数 cnt[1-num] 以下であれば、res を 1 増やします
• 最後に res を返します

このアルゴリズムが正しく機能するのは、現在位置で終わる有効な部分文字列が存在するのは「現在の文字の連続数が、直前の異なる文字の連続数を超えない場合」と限られるからです。例えば "0011" の場合、最初の '1' の時点では cnt[1]=1 ≤ cnt[0]=2 なので "01" が成立し、次の '1' の時点でも cnt[1]=2 ≤ cnt[0]=2 なので "0011" が成立します。このように各位置での判定が積み重なり、全体の答えが得られます。

実装例(C++)

#include <bits/stdc++.h>
using namespace std;
class Solution {
public:
    int countBinarySubstrings(string s) {
        int cnt[2] = { 0 };
        int res = 0;
        for (int i = 0; i < s.length(); ++i) {
            int num = s[i] - '0';
            if (i == 0 || s[i] != s[i - 1])
                cnt[num] = 0;
            ++cnt[num];
            if (cnt[num] <= cnt[1 - num])
                ++res;
        }
        return res;
   }
};
main(){
    Solution ob;
    cout << (ob.countBinarySubstrings("11001100"));
}

入力

"11001100"

出力

6

まとめ

この手法では文字列を一度だけ走査すればよいため、時間計算量は O(n)、追加の記憶領域も定数 O(1) で済みます。すべての部分文字列を実際に生成して検証する代わりに、「連続する同一文字のグループ長を比較する」という発想で効率よく答えを求められるのが最大のポイントです。