C++でバイナリ部分文字列をカウントする

文字列sがあるとすると、同じ数の0と1を持つ連続するサブ文字列の数を見つける必要があり、これらのサブ文字列のすべての0とすべての1が連続してグループ化されます。サブストリングが複数回発生する場合は、発生回数がカウントされます。

したがって、入力が「11001100」の場合、サブストリングは「1100」、「10」、「0011」、「01」、「1100」、「10」であるため、出力は6になります。

これを解決するには、次の手順に従います-

• サイズ2の配列cntを定義し、これに0を入力します
• res：=0
• iを初期化する場合：=0、i
• num：=s[i]-「0」のASCII
• iが0と同じか、s[i]がs[i-1]と等しくない場合、-
  • cnt [num]：=0
• （cnt [num]を1増やします）
• cnt [num] <=cnt [1-num]の場合、-
  • （解像度を1増やします）

理解を深めるために、次の実装を見てみましょう-

例

#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