12_jan

/\*
A parentheses string is a non-empty string consisting only of '(' and ')'. It is valid if any of the following conditions is true:

It is ().
It can be written as AB (A concatenated with B), where A and B are valid parentheses strings.
It can be written as (A), where A is a valid parentheses string.
You are given a parentheses string s and a string locked, both of length n. locked is a binary string consisting only of '0's and '1's. For each index i of locked,

If locked[i] is '1', you cannot change s[i].
But if locked[i] is '0', you can change s[i] to either '(' or ')'.
Return true if you can make s a valid parentheses string. Otherwise, return false.

Example 1:

Input: s = "))()))", locked = "010100"
Output: true
Explanation: locked[1] == '1' and locked[3] == '1', so we cannot change s[1] or s[3].
We change s[0] and s[4] to '(' while leaving s[2] and s[5] unchanged to make s valid.
\*/

//approch 1

class Solution {
public:
bool canBeValid(string s, string locked) {
int n = s.length();

    if (n % 2 != 0)
        return false;

    stack<int> open;
    stack<int> openClose;

    for (int i = 0; i < n; i++) {
        if (locked[i] == '0') {
            openClose.push(i);
        } else if (s[i] == '(') {
            open.push(i);
        } else if (s[i] == ')') {
            if (!open.empty()) {
                open.pop();
            } else if (!openClose.empty()) {
                openClose.pop();
            } else {
                return false;
            }
        }
    }

    while (!open.empty() && !openClose.empty() && open.top() < openClose.top()) {
        open.pop();
        openClose.pop();
    }

    return open.empty();

    }

};

//approch 2
class Solution {
public:
bool canBeValid(string s, string locked) {
int n = s.length();
if (n % 2 != 0) {
return false; // Odd length cannot form valid parentheses
}

        // Left-to-right pass: Ensure there are enough open brackets
        int openCount = 0;
        for (int i = 0; i < n; i++) {
            if (s[i] == '(' || locked[i] == '0') {
                openCount++;
            } else { // s[i] == ')' and locked[i] == '1'
                openCount--;
            }
            if (openCount < 0) {
                return false; // Too many ')' encountered
            }
        }

        // Right-to-left pass: Ensure there are enough close brackets
        int closeCount = 0;
        for (int i = n - 1; i >= 0; i--) {
            if (s[i] == ')' || locked[i] == '0') {
                closeCount++;
            } else { // s[i] == '(' and locked[i] == '1'
                closeCount--;
            }
            if (closeCount < 0) {
                return false; // Too many '(' encountered
            }
        }

        return true;
    }

};