Tách chuỗi cân bằng trong C++

Chuỗi cân bằng: số lượng 'L' và 'R' bằng nhau. Cho chuỗi cân bằng s, tách thành số lượng lớn nhất các chuỗi con cân bằng.

Ví dụ

s = "RLRRLLRLRL" → 4 chuỗi con: "RL", "RRLL", "RL", "RL"

s = "RLLLLRRRLR" → 3 chuỗi con

Thuật toán đếm (Greedy)

Duyệt chuỗi, giữ counter: gặp 'R' +1, gặp 'L' -1. Khi counter = 0 → tìm được 1 chuỗi cân bằng, tăng kết quả, reset counter.

Chương trình mẫu

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

class Solution {
public:
    int balancedStringSplit(string s) {
        int balance = 0, count = 0;
        for (char c : s) {
            if (c == 'R') balance++;
            else balance--; // 'L'
            if (balance == 0) count++;
        }
        return count;
    }
};

int main() {
    Solution ob;
    cout << ob.balancedStringSplit("RLLLLRRRLR") << endl; // 3
    cout << ob.balancedStringSplit("RLRRLLRLRL") << endl; // 4
    return 0;
}

Kết quả

3
4

Giải thích: Mỗi khi balance về 0, ta có một chuỗi con cân bằng hoàn chỉnh. Tách ngay tại đó cho số lượng tối đa (greedy).

Độ phức tạp: O(n) thời gian, O(1) không gian. Rất hiệu quả.

Lưu ý: Code gốc dùng lồng vòng for phức tạp O(n²), đã tối ưu hóa thành O(n) một vòng lặp.