Tìm số vị trí cân bằng trong chuỗi trong C++

Cho chuỗi. Tìm số vị trí cân bằng: chia chuỗi thành 2 phần trái/phải chứa cùng tập ký tự (không quan tâm tần suất). Ví dụ: "ABAABA" → 3 vị trí: AB|AABA, ABA|ABA, ABAA|BA.

Thuật toán hiệu quả

1. Đếm tần suất tất cả ký tự vào mảng right[]
2. Duyệt trái sang phải:
   • Tăng left[ky_tu], giảm right[ky_tu]
   • Kiểm tra: mọi ký tự có trong left (count>0) cũng có trong right (count>0) và ngược lại
   • Nếu đúng → tăng kết quả

Chương trình C++

#include <iostream> 
#include <algorithm> 
#define MAX_CHAR 256 
using namespace std; 

int countBalancePoints(string str) {
    int left[MAX_CHAR] = {0};
    int right[MAX_CHAR] = {0};
    
    for (int i = 0; i < str.length(); i++)
        right[str[i]]++;
    
    int count = 0;
    for (int i = 0; i < str.length(); i++) {
        left[str[i]]++;
        right[str[i]]--;
        
        int j;
        for (j = 0; j < MAX_CHAR; j++) {
            if ((left[j] == 0 && right[j] != 0) || (left[j] != 0 && right[j] == 0))
                break;
        }
        if (j == MAX_CHAR)
            count++;
    }
    return count;
}

int main() {
    char str[] = "ABAABA";
    cout << "Number of balance points: " << countBalancePoints(str);
}

Kết quả

Number of balance points: 3

Độ phức tạp

• Thời gian: O(n × 256) ≈ O(n)
• Không gian: O(256) = O(1)