Hiểu bài toán

Xâu nhị phân $S$ chỉ bao gồm các ký tự '0' và '1'. Nhiệm vụ của bạn là tìm độ dài dãy liên tiếp các ký tự '0' dài nhất trong xâu $S$. Ví dụ: với xâu '10011010001', dãy '0' dài nhất có độ dài 3 (từ các ký tự thứ 9 đến 11).

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

Cách Duyệt tất cả các dãy con

void sub1(string s) {
    int ans = 0, dem = 0;
    FOR(i, 0, (int)s.size() - 1) {
        dem = 0;
        FOR(j, i, (int)s.size() - 1) {
            if (s[j] == '0') dem++;
            else {
                ans = max(ans, dem);
                dem = 0;
            }
        }
    }
    if (dem) ans = max(ans, dem);
    cout << ans;
}

• Time Complexity: O(n^2)
• Space Complexity: O(1)

Phương pháp này sử dụng hai vòng lặp lồng nhau để duyệt qua tất cả các dãy con. Với mỗi vị trí bắt đầu i, nó đếm số lượng '0' liên tiếp cho đến khi gặp '1'. Tuy nhiên, đoạn code mẫu bị lỗi logic (gán dem = 0 ở vòng lặp ngoài) dẫn đến kết quả không chính xác. Ý tưởng chung là cạn kiệt tất cả khả năng, nhưng độ phức tạp O(n^2) quá cao và không hiệu quả cho dữ liệu lớn.

Cách Đếm số 0 liên tiếp (Duyệt một lần)

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    string st;
    cin >> st;
    int d = 0, s = 0;
    for (int i = 0; i < st.size(); i++) {
        if (st[i] == '0') d++;
        else {
            s = max(s, d);
            d = 0;
        }
    }
    cout << max(s, d);
    return 0;
}

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

Đây là thuật toán tối ưu. Ta duyệt xâu từ trái sang phải, dùng biến d để đếm độ dài dãy '0' hiện tại. Khi gặp ký tự '1', ta cập nhật kết quả lớn nhất (s) và reset biến đếm d về 0. Sau khi vòng lặp kết thúc, ta so sánh thêm một lần nữa với d để xử lý trường hợp xâu kết thúc bằng các ký tự '0'.

Cách Sử dụng stringstream

void sub2(string s) {
    FOR(i, 0, (int)s.size() - 1) {
        if (s[i] != '0') s[i] = ' ';
    }
    stringstream ss(s); string tmp;
    int ans = 0;
    while (ss >> tmp) ans = max(ans, (int)tmp.size());
    cout << ans;
}

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

Phương pháp này biến đổi xâu bằng cách thay thế tất cả ký tự '1' thành dấu cách. Sau đó, sử dụng stringstream để tách xâu thành các chuỗi con dựa trên dấu cách (tương ứng với các dãy '0'). Cuối cùng tìm độ dài lớn nhất trong các chuỗi con này. Cách này creative nhưng tốn bộ nhớ hơn và chậm hơn do thao tác biến đổi xâu và phân tích.

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

Bài học kinh nghiệm

• Bài toán này là bài toán kinh điển về 'Maximum consecutive zeros'.
• Cần phân biệt giữa độ dài dãy liên tiếp dài nhất và tổng số lượng '0'.
• Chỉ cần duyệt qua xâu một lần (Single Pass) là đủ để giải quyết bài toán tối ưu.

Lỗi thường gặp

• Quên kiểm tra dãy '0' cuối cùng nếu xâu kết thúc bằng '0' (cần kiểm tra max(s, d) sau vòng lặp).
• Lỗi logic trong code tham khảo Solution 1: biến dem được gán lại bằng 0 ở đầu vòng lặp ngoài, làm mất hết thông tin đếm từ các vị trí trước.