Editorial for parenthesis: Biến đổi chuỗi thành dãy ngoặc đúng

Hiểu bài toán

Cho xâu ký tự S chỉ gồm '(', ')' và ''. Nhiệm vụ là xác định xem có thể thay thế các ký tự '' bằng '(' hoặc ')' sao cho xâu kết quả là một dãy ngoặc đúng hay không.

Một dãy ngoặc đúng (valid parentheses) được định nghĩa đệ quy:

• Rỗng là hợp lệ.
• (A) là hợp lệ nếu A là hợp lệ.
• AB là hợp lệ nếu A và B đều hợp lệ.

Về cơ bản, ta cần kiểm tra xem có cách gán giá trị cho '*' để:

1. Tổng số '(' bằng tổng số ')' (độ dài chẵn).
2. Tại mọi điểm trong xâu, số '(' duyệt qua phải luôn lớn hơn hoặc bằng số ')' (số ngoặc mở không được phép âm).

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

Cách Quy hoạch động theo miền giá trị số ngoặc mở

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

bool checkValid(string s) {
    int n = s.size();
    if (n % 2 == 1) return false;

    int minOpen = 0, maxOpen = 0;

    for (char c : s) {
        if (c == '(') {
            minOpen++;
            maxOpen++;
        } else if (c == ')') {
            minOpen--;
            maxOpen--;
        } else if (c == '*') {
            minOpen--; // Giả sử là ')'
            maxOpen++; // Giả sử là '('
        }

        // Nếu số ngoặc mở tối đa < 0, tức là không cách nào cứu vãn được
        if (maxOpen < 0) return false;

        // Số ngoặc mở tối thiểu không được phép âm
        if (minOpen < 0) minOpen = 0;
    }

    return (minOpen == 0);
}

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

Đây là phương pháp tối ưu nhất dựa trên ý tưởng theo dõi miền giá trị của số ngoặc mở.

Ta duy trì hai biến:

• maxOpen: Số lượng ngoặc mở nhiều nhất có thể có tại điểm hiện tại (nếu ta ưu tiên biến '*' thành '(').
• minOpen: Số lượng ngoặc mở ít nhất có thể có tại điểm hiện tại (nếu ta ưu tiên biến '*' thành ')').

Quy tắc cập nhật:

• Gặp '(': Cả hai đều tăng 1.
• Gặp ')': Cả hai đều giảm 1.
• Gặp '*': maxOpen tăng 1 (nếu là '('), minOpen giảm 1 (nếu là ')').

Kiểm tra:

1. Nếu maxOpen < 0: Ngay cả khi dùng hết '*' để tạo '(' vẫn bị thừa ')'. Dừng ngay, trả về NO.
2. Nếu minOpen < 0: Ta đã dùng quá nhiều '' cho ')'. Vì ta có thể tùy ý chọn, ta có thể chuyển một số '' đó thành '(' để số ngoặc mở về 0. Do đó ta reset minOpen = 0.
3. Cuối cùng, nếu minOpen == 0, nghĩa là tồn tại ít nhất một cách gán sao cho số ngoặc mở về 0.

Cách Brute Force (Tuyến tính)

// Pseudocode minh họa logic thay thế
// Chỉ chạy được cho N rất nhỏ (N <= 15)
void brute_force(string s) {
    int n = s.size();
    vector<int> stars;
    for(int i=0; i<n; i++) if(s[i]=='*') stars.push_back(i);

    int m = stars.size();
    for(int mask=0; mask < (1<<m); mask++) {
        string temp = s;
        for(int i=0; i<m; i++) {
            temp[stars[i]] = (mask & (1<<i)) ? '(' : ')';
        }
        if(isValid(temp)) {
            cout << "YES";
            return;
        }
    }
    cout << "NO";
}

bool isValid(string s) {
    int balance = 0;
    for(char c : s) {
        if(c == '(') balance++;
        else balance--;
        if(balance < 0) return false;
    }
    return balance == 0;
}

• Time Complexity: O(2^K * N) (K là số lượng dấu sao)
• Space Complexity: O(N)

Đây là cách tiếp cận trực quan nhất. Ta dùng đệ quy hoặc vòng lặp bitmask để thử tất cả các cách thay thế '*' bằng '(' hoặc ')'. Với mỗi cách thay thế, ta kiểm tra xem xâu thu được có phải là dãy ngoặc đúng hay không.

Cách kiểm tra dãy ngoặc đúng:

• Duyệt từ trái sang phải, duy trì biến balance.
• Gặp '(' thì balance++, gặp ')' thì balance--.
• Nếu tại bất kỳ đâu balance < 0, dãy sai.
• Cuối cùng nếu balance == 0, dãy đúng.

Phương pháp này chỉ khả thi với N <= 20.

Cách Xử lý riêng '*' và ')' (Phân tích thống kê)

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

void solve() {
    string s;
    cin >> s;
    int n = s.length();
    if (n % 2 == 1) {
        cout << "NO\n";
        return;
    }

    // Đếm số lượng '*' có thể dùng để đóng ngoặc (từ phải sang trái)
    vector<int> suf(n + 1, 0);
    for (int i = n - 1; i >= 0; i--) {
        suf[i] = suf[i+1] + (s[i] == '*' ? 1 : 0);
    }

    int open = 0;
    int star = 0; // Số '*' có thể dùng để đóng (từ trái tới)

    for (int i = 0; i < n; i++) {
        if (s[i] == '(') {
            open++;
        } else if (s[i] == ')') {
            open--;
        } else {
            star++;
        }

        // Kiểm tra tại điểm này:
        // Số '(' bắt buộc phải có (open) 
        // Số '*' có thể dùng để cân bằng (star)
        // Số '*' còn lại ở bên phải (suf[i+1])

        // Logic này hơi phức tạp để diễn giải ngắn gọn, 
        // nhưng về cơ bản là kiểm tra xem có đủ '*' để đóng các '(' đang mở không.
        if (open < 0) {
             // Cần dùng '*' để đóng
             if (star > 0) {
                 star--;
                 open++;
             } else {
                 cout << "NO\n";
                 return;
             }
        }
    }

    // Cuối cùng phải cân bằng
    if (open == 0) cout << "YES\n";
    else cout << "NO\n";
}

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

Đây là một cách tiếp cận khác O(N), sử dụng nhiều bộ nhớ hơn một chút.

Ý tưởng:

1. Duyệt từ phải sang trái để tạo mảng phụ suf, đếm số lượng '*' ở phía sau mỗi vị trí.
2. Duyệt từ trái sang phải, duy trì:
   • open: Số '(' đang cần đóng.
   • star: Số '' đã gặp nhưng chưa sử dụng.
   • Khi gặp ')', nếu open > 0, dùng '(' để đóng. Nếu open == 0, phải dùng '' (nếu có) để đóng vai trò '('.
   • Khi gặp '*', thêm vào star.
3. Cuối cùng, kiểm tra xem có thể cân bằng toàn bộ hay không.

Lưu ý: Code minh họa trên chỉ là một biến thể, giải pháp chính xác thường cần nhiều bước logic hơn một chút để xử lý việc dùng '*' làm '(' hay ')' linh hoạt.

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

Bài học kinh nghiệm

• Vấn đề có thể giảm xuống thành bài toán kiểm tra sự tồn tại của một chuỗi con số (số ngoặc mở) sao cho tại mọi thời điểm giá trị >= 0 và cuối cùng bằng 0.
• Dấu '*' đóng vai trò 'bộ đệm', có thể trở thành '(' (tăng độ dài) hoặc ')' (giảm độ dài). Do đó, ta chỉ cần quan tâm đến biên trên và biên dưới của độ dài chuỗi ngoặc mở.

Lỗi thường gặp

• Quên kiểm tra độ dài xâu là số chẵn. Nếu độ dài lẻ, chắc chắn không thể là dãy ngoặc đúng.
• Lỗi logic khi cập nhật minOpen: Sau khi trừ đi (do gặp ')' hoặc ''), nếu minOpen âm, ta phải coi việc này là không hợp lệ và gán lại về 0 (vì ta có thể chọn cách gán '' thành '(' để tránh việc này).
• Chỉ kiểm tra điều kiện cân bằng ở cuối chuỗi mà không kiểm tra trong quá trình duyệt (ví dụ: xâu bắt đầu bằng '))))' dù có '*' ở sau cũng không thể cứu vãn).