Đếm chuỗi con có số lượng 0, 1, 2 bằng nhau trong C++

Cho chuỗi str chỉ chứa '0', '1', '2'. Đếm chuỗi con có số lượng 3 ký tự này bằng nhau. Ví dụ "12012" → "120", "201", "012" (3 chuỗi con).

Ví dụ

Đầu vào: str = "112200120"
Đầu ra: 5.

Đầu vào: str = "12012"
Đầu ra: 3.

Giải thuật (Prefix Difference + Hash Map)

Giữ 3 biến đếm c0, c1, c2. Tính hiệu d1 = c0 - c1, d2 = c0 - c2. Dùng map<pair<int,int>, int> đếm tần suất cặp (d1, d2). Khởi tạo map[(0,0)] = 1. Duyệt chuỗi, cập nhật đếm, cộng tần suất cặp hiệu hiện tại vào kết quả, tăng tần suất cặp hiệu.

Ví dụ triển khai

#include <bits/stdc++.h>
using namespace std;

int count_string(string str, int len) {
    map<pair<int,int>, int> mp;
    mp[{0,0}] = 1;
    int c0 = 0, c1 = 0, c2 = 0;
    int count = 0;
    for (int i = 0; i < len; i++) {
        if (str[i] == '0') c0++;
        else if (str[i] == '1') c1++;
        else c2++;
        int d1 = c0 - c1;
        int d2 = c0 - c2;
        count += mp[{d1, d2}];
        mp[{d1, d2}]++;
    }
    return count;
}

int main() {
    string str = "112200120";
    int len = str.length();
    cout << "Count of Substrings with equal number of 0s, 1s and 2s are: " << count_string(str, len);
    return 0;
}

Kết quả

Count of Substrings with equal number of 0s, 1s and 2s are: 5