Đếm chuỗi con nhị phân trong C ++

Giả sử chúng ta có một chuỗi s, chúng ta phải tìm số lượng các chuỗi con liền kề có cùng số 0 và 1, và tất cả các 0 và tất cả các 1 trong các chuỗi con này được nhóm liên tiếp. Nếu các chuỗi con xảy ra nhiều lần được tính số lần chúng xuất hiện.

Vì vậy, nếu đầu vào là "11001100", thì đầu ra sẽ là 6, vì các chuỗi con là "1100", "10", "0011", "01", "1100", "10".

Để giải quyết vấn đề này, chúng tôi sẽ làm theo các bước sau -

• Xác định cnt mảng có kích thước 2 và điền vào giá trị này bằng 0
• res:=0
• để khởi tạo i:=0, khi i <độ dài của s, cập nhật (tăng i lên 1), thực hiện -
  • num:=s [i] - ASCII của '0'
  • nếu tôi giống với 0 hoặc s [i] không bằng s [i - 1], thì -
    • cnt [num]:=0
  • (tăng cnt [num] lên 1)
  • nếu cnt [num] <=cnt [1 - num], thì -
    • (tăng độ phân giải lên 1)
• trả lại res

Hãy cùng chúng tôi xem cách triển khai sau để hiểu rõ hơn -

Ví dụ

#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"));
}

Đầu vào

"11001100"

Đầu ra

6