Hiểu bài toán

Bài toán yêu cầu tìm độ dài lớn nhất của một xâu con liên tiếp Sx sao cho giá trị value(Sx) ≤ C. Giá trị của một xâu T độ dài k được định nghĩa là số lượng cặp (i, j) với 1 ≤ i < j ≤ k sao cho Ti = 'a' và Tj = 'b'. Nói cách khác, đó là số lượng cặp ký tự 'a' đứng trước 'b' trong xâu. Với N lên tới 10^6 và C lên tới 10^18, chúng ta cần một giải pháp hiệu quả.

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

Cách Two Pointers (Sliding Window)

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

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

    int N;
    long long C;
    cin >> N >> C;
    string S;
    cin >> S;

    int l = 0;
    long long cnt_a = 0, cnt_b = 0, value = 0, res = 0;

    for (int r = 0; r < N; ++r) {
        if (S[r] == 'a') cnt_a++;
        else if (S[r] == 'b') {
            value += cnt_a;
            cnt_b++;
        }

        while (value > C) {
            if (S[l] == 'a') {
                cnt_a--;
                value -= cnt_b;
            } else if (S[l] == 'b') {
                cnt_b--;
            }
            l++;
        }

        res = max(res, 1LL * (r - l + 1));
    }

    cout << res << '\n';
    return 0;
}

• Time Complexity: O(N)
• Space Complexity: O(N) (lưu trữ xâu S)

Đây là cách tiếp cận chính xác và hiệu quả nhất. Ta sử dụng kỹ thuật hai con trỏ (sliding window) với con trỏ phải r để duyệt qua các xâu con kết thúc tại r. Dùng các biến cnt_a, cnt_b để đếm số lượng 'a' và 'b' trong đoạn đang xét, và value để lưu số cặp (a, b). Khi thêm ký tự S[r] vào:

• Nếu là 'a': tăng cnt_a.
• Nếu là 'b': tăng cnt_b và tăng value thêm cnt_a (vì tất cả các 'a' đã có trong đoạn đều tạo thành cặp với 'b' mới này). Sau đó, nếu value vượt quá C, ta thu hẹp đoạn từ bên trái bằng cách di chuyển con trỏ l sang phải và cập nhật lại cnt_a, cnt_b, value cho đến khi value ≤ C. Độ dài đoạn hiện tại là r - l + 1. Ta cập nhật kết quả最大值. Mỗi phần tử được thêm vào và loại bỏ tối đa 1 lần nên độ phức tạp là O(N).

Cách Brute Force (Đơn giản hóa)

// Ví dụ minh họa logic tính value
// Cấu trúc tương tự Approach 1 nhưng không có tối ưu sliding window
count_a = 0; count_b = 0; value = 0;
for(int i = 0; i < N; i++) {
    for(int j = i; j < N; j++) {
        if(S[j] == 'a') count_a++;
        else if(S[j] == 'b') {
            value += count_a;
            count_b++;
        }
        // Kiem tra value <= C
    }
    // Reset count
}

• Time Complexity: O(N^2)
• Space Complexity: O(N)

Đây là cách tiếp cận trực quan nhất nhưng không khả thi với N=10^6. Ta thử tất cả các đoạn con [i, j], tính giá trị value của nó và tìm độ dài lớn nhất thỏa mãn. Mỗi đoạn con con đều phải duyệt lại từ đầu để tính value, dẫn đến độ phức tạp O(N^2).

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

Bài học kinh nghiệm

• Value của đoạn con [L, R] có thể tính toán delta (sự thay đổi) khi ta thêm một ký tự vào cuối đoạn hoặc remove một ký tự từ đầu đoạn.
• Khi thêm 'b' vào cuối đoạn, value tăng lên số lượng 'a' đang có trong đoạn.
• Khi xóa 'a' khỏi đầu đoạn, value giảm đi số lượng 'b' đang có trong đoạn (vì tất cả các cặp tạo bởi 'a' này với các 'b' sau đó sẽ bị loại bỏ).

Lỗi thường gặp

• Sử dụng biến kiểu int để lưu trữ C hoặc giá trị value, trong khi đề bài cho C lên tới 10^18. Phải dùng long long.
• Lỗi logic cập nhật sai số lượng cặp khi trượt cửa sổ. Ví dụ: khi loại bỏ 'a' ở đầu, value phải giảm đi cnt_b hiện tại của đoạn, không phải 1.
• Xử lý sai trường hợp xâu con rỗng hoặc các ký tự khác ngoài 'a' và 'b' (dù đề bài chỉ nói có thể có chữ cái Latin in thường, nhưng code mẫu chỉ xử lý 'a' và 'b', các ký tự khác có thể coi là không ảnh hưởng hoặc bị bỏ qua).