Hiểu bài toán

Xét một chuỗi $S$ độ dài $N$ chỉ chứa các ký tự 'a' và 'b'. Gọi $balance(i, j)$ là hiệu số số lượng ký tự 'a' trừ đi số lượng ký tự 'b' trong đoạn con từ chỉ số $i$ đến $j$ (1-indexed). Bài toán yêu cầu đếm số lượng cặp chỉ số $(i, j)$ sao cho $1 \le i \le j \le N$ và $balance(i, j) = 0$. Nói cách khác, cần tìm số lượng đoạn con có số lượng 'a' bằng số lượng 'b'.

Các cách tiếp cận

Cách Hash Map (Tần số)

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

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);

    freopen("DANCE.INP", "r", stdin);
    freopen("DANCE.OUT", "w", stdout);

    int n;
    cin >> n;
    string s;
    cin >> s;

    unordered_map<long long, long long> cnt;
    long long balance = 0;
    cnt[0] = 1;

    for (char c : s) {
        if (c == 'a') balance++;
        else balance--;
        cnt[balance]++;
    }

    long long res = 0;
    for (auto &p : cnt) {
        long long f = p.second;
        res += f * (f - 1) / 2;
    }

    cout << res;
    return 0;
}

• Time Complexity: O(n)
• Space Complexity: O(n)

Cách tiếp cận này dựa trên việc sử dụng mảng tần số (hoặc hash map) để đếm số lần xuất hiện của mỗi tổng tiền tố (balance).

1. Bước 1: Duyệt qua chuỗi để tính tổng tiền tố tại mỗi vị trí. Biến balance lưu tổng tiền tố hiện tại. Nếu gặp 'a' thì cộng 1, gặp 'b' thì trừ 1.
2. Bước 2: Trong quá trình duyệt, ta dùng một hash map cnt để lưu số lần xuất hiện của mỗi giá trị balance. Ta khởi tạo cnt[0] = 1 để xử lý các đoạn con bắt đầu từ đầu chuỗi.
3. Bước 3: Nếu tại một vị trí, tổng tiền tố có giá trị là $x$ và đã xuất hiện $k$ lần trước đó (bao gồm cả tổng tiền tố 0 ban đầu), thì có $k$ đoạn con kết thúc tại vị trí hiện tại có tổng bằng 0.
4. Bước 4 (Cách tính tổng hợp): Thay vì cộng dồn ngay khi duyệt, ta có thể duyệt một lần để đếm tần số, rồi dùng công thức kết hợp $C(f, 2) = \frac{f(f-1)}{2}$ cho mỗi tần số $f$.

Ví dụ: Chuỗi "ab". Các tổng tiền tố: 0 (ban đầu), 1 (sau 'a'), 0 (sau 'b').

• cnt[0] = 2, cnt[1] = 1.
• Kết quả: $C(2, 2) + C(1, 2) = 1 + 0 = 1$. (Đoạn con "ab").

Cách Prefix Sum & Duyệt

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

int main() {
    ifstream fin("DANCE.INP");
    ofstream fout("DANCE.OUT");

    int n;
    fin >> n;
    string s;
    fin >> s;

    vector<int> pre(n+1, 0);
    for(int i=0; i<n; i++){
        pre[i+1] = pre[i] + (s[i]=='a' ? 1 : -1);
    }

    map<int, long long> freq;
    freq[0] = 1;
    long long ans = 0;
    for(int i=1; i<=n; i++){
        ans += freq[pre[i]];
        freq[pre[i]]++;
    }

    fout << ans << "\n";
    return 0;
}

• Time Complexity: O(n log n)
• Space Complexity: O(n)

Phương pháp này sử dụng mảng tổng tiền tố (Prefix Sum) và một cấu trúc cây (map) để đếm.

1. Tính Prefix Sum: Tạo mảng pre độ dài $N+1$. pre[i] thể hiện hiệu số 'a' - 'b' của $i$ phần tử đầu tiên. pre[0] = 0.
2. Duyệt tìm cặp: Vòng lặp duyệt qua $i$ từ 1 đến $N$. Với mỗi pre[i], ta cần tìm số lượng chỉ số $j < i$ sao cho pre[j] == pre[i].
3. Cấu trúc dữ liệu: Dùng map (hoặc hash map) để lưu tần số của các tổng tiền tố đã gặp. Tại mỗi bước, ta cộng freq[pre[i]] vào kết quả (vì mỗi tổng tiền tố đã xuất hiện trước đó tạo thành một đoạn con cân bằng với hiện tại), sau đó tăng tần số của pre[i] lên 1.

So sánh với Solution 1: Logic tương tự nhưng cách triển khai này minh họa rõ hơn việc "tìm số cặp bằng cách cộng dồn". Solution 1 (cách 1) tính tần số trước rồi dùng công thức kết hợp, cách này cộng dồn trực tiếp trong quá trình duyệt.

Phân tích độ phức tạp

Bài học kinh nghiệm

• Bài toán có thể biến đổi thành bài toán tìm số cặp chỉ số $(i, j)$ sao cho tổng tiền tố tại $j$ bằng tổng tiền tố tại $i-1$.
• Kỹ thuật hash map (đếm tần số) là phương pháp hiệu quả nhất để giải quyết bài toán này với độ phức tạp O(n).

Lỗi thường gặp

• Lỗi tràn số biên (integer overflow) khi tính tổng nếu không sử dụng biến có độ rộng lớn (long long).
• Xử lý sai trường hợp tổng tiền tố bằng 0 ngay từ đầu (cần khởi tạo tần số của 0 là 1).