Check if a Parentheses String Can Be Valid

The main trick to this question, is that a parentheses string will not be valid, if there are orphan locked parentheses (locked parentheses that are impossible to match).

Therefore, the easiest solution is to take a greedy approach, iterating s twice (once forwards and once backwards), to check that all locked parentheses are able to be matched (with a corresponding locked parentheses or any unlocked parentheses).

code

class Solution {
public:
    bool canBeValid(string s, string locked) {
        if (s.size()%2 != 0) {
            return false;
        }

        int count = 0;
        for (int i = 0; i < s.size(); ++i) {
            if (s[i] == '(' || locked[i] == '0') {
                ++count;
            } else {
                --count;
            }

            if (count < 0) {
                return false;
            }
        }

        count = 0;
        for (int i = s.size()-1; i >= 0; --i) {
            if (s[i] == ')' || locked[i] == '0') {
                ++count;
            } else {
                --count;
            }

            if (count < 0) {
                return false;
            }
        }
        return true;
    }
};

complexity

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