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

Mô tả bài toán

Cho chuỗi nhị phân s, đếm số chuỗi con liên tiếp có số lượng 0 và 1 bằng nhau, và tất cả 0 cũng như 1 đều nhóm liên tiếp (ví dụ: "1100", "10", "0011", "01").

Ví dụ: "11001100" → 6 chuỗi con: "1100", "10", "0011", "01", "1100", "10".

Giải pháp (Đếm nhóm liên tiếp)

• Duyệt chuỗi, đếm độ dài nhóm hiện tại của ký tự num (0 hoặc 1).
• Khi chuyển nhóm (ký tự khác trước đó), reset bộ đếm nhóm hiện tại.
• Nếu độ dài nhóm hiện tại ≤ độ dài nhóm trước → tìm thấy một chuỗi con hợp lệ → tăng kết quả.

Ví dụ minh họa

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

int main() {
    Solution ob;
    cout << ob.countBinarySubstrings("11001100");
    return 0;
}

Đầu vào

"11001100"

Đầu ra

6