TEST CASES:
1. s = "(()", locked = "001" -> false (độ dài lẻ)

2. s = "(())", locked = "1111" -> true (đã hợp lệ)

3. s = "))()", locked = "0000" -> true (có thể đổi thành "(())")

4. s = ")(", locked = "11" -> false (không đổi được, bị khóa)

5. s = "())(", locked = "0011" -> true (đổi 2 kí tự đầu)

class Solution {
public:
    bool canBeValid(string s, string locked) {
        // Bước 1: Check điều kiện cơ bản - độ dài phải chẵn
        if (s.length() % 2 != 0) return false;

        // Khởi tạo hai stack để theo dõi
        stack<int> openStack, freeStack;

        // Bước 2: Duyệt từng ký tự trong xâu
        for (int i = 0; i < s.length(); i++) {
            if (locked[i] == '0') {
                // Case 1: Ký tự có thể thay đổi -> lưu vào freeStack
                freeStack.push(i);
            } 
            else if (s[i] == '(') {
                // Case 2: Dấu mở ngoặc bị khóa -> lưu vào openStack
                openStack.push(i);
            } 
            else { // Case 3: s[i] == ')' và bị khóa
                // Thử ghép với dấu mở ngoặc gần nhất
                if (!openStack.empty()) {
                    openStack.pop();
                }
                // Không có '(' -> dùng ký tự tự do
                else if (!freeStack.empty()) {
                    freeStack.pop();
                }
                // Không có cách nào để ghép -> invalid
                else {
                    return false;
                }
            }
        }

        // Bước 3: Xử lý các dấu mở ngoặc còn thừa
        while (!openStack.empty() && !freeStack.empty()) {
            // Check vị trí: ký tự tự do phải nằm sau dấu mở ngoặc
            if (openStack.top() > freeStack.top()) return false;
            openStack.pop();
            freeStack.pop();
        }

        // Cuối cùng: nếu còn dấu mở ngoặc -> invalid
        return openStack.empty();
    }
};

int main() {
    Solution sol;

    // Test case 1: Có thể biến đổi
    cout << "Test 1: " << (sol.canBeValid("())", "010") ? "TRUE" : "FALSE") << endl;
    // Kết quả mong đợi: False

    // Test case 2: Không thể biến đổi
    cout << "Test 2: " << (sol.canBeValid(")(", "11") ? "TRUE" : "FALSE") << endl;
    // Kết quả mong đợi: FALSE

    // Test case phức tạp
    cout << "Test 3: " << (sol.canBeValid("())(())", "0000000") ? "TRUE" : "FALSE") << endl;
    // Kết quả mong đợi: TRUE

    return 0;
}