Check if a Parentheses String Can Be Valid

Intuitionwhy two directional feasibility checks are enough

A valid parentheses string has two directional requirements. Reading from left to right, no prefix may contain more closing parentheses than opening parentheses, because a closing parenthesis needs an earlier opening parenthesis. Reading from right to left, no suffix may contain more opening parentheses than closing parentheses, because an opening parenthesis needs a later closing parenthesis.

An unlocked position can help either requirement. During the left-to-right scan, pretend every unlocked position is an opening parenthesis, because that gives the prefix as much protection as possible against a locked closing parenthesis. During the right-to-left scan, pretend every unlocked position is a closing parenthesis for the symmetric reason. If either favorable scan still becomes impossible, no assignment can repair it. With even length, these two checks also ensure that the flexible positions can be assigned consistently.

Approachturning each direction into one balance check

1. 1If the length n is odd, return false immediately, because every valid parentheses pair consumes exactly two positions and no position can remain unmatched.
2. 2Scan from left to right with balance equal to the number of currently available opening parentheses. Add one for a locked opening parenthesis or any unlocked position, and subtract one for a locked closing parenthesis, because an unlocked position can be chosen as an opening parenthesis in this scan.
3. 3If balance becomes negative during the left scan, return false. That prefix has more forced closing parentheses than positions that can serve as opening parentheses, so no assignment can make that prefix valid.
4. 4Reset balance and scan from right to left. Add one for a locked closing parenthesis or any unlocked position, and subtract one for a locked opening parenthesis, because an unlocked position can be chosen as a closing parenthesis in this direction.
5. 5If balance becomes negative during the right scan, return false. That suffix has more forced opening parentheses than positions that can serve as closing parentheses, so some opening parenthesis would remain unmatched on its right.
6. 6Return true after both scans. The first pass rules out impossible prefixes, the second rules out impossible suffixes, and the even-length check guarantees the final number of opening and closing parentheses can be equal.

Complexityconstant working memory despite two passes

Annotated solutionC++ · two greedy scans · constant extra space

#include <string>
using namespace std;

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

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

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

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

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

        return true;
    }
};

The two conditions inside the scans deliberately differ. In the first loop, an unlocked position contributes as '(', since that is the choice that best protects a prefix. In the second loop, the same position contributes as ')', since that is the choice that best protects a suffix. The negative check is the important placement: it rejects the moment a direction has run out of possible matches, rather than waiting until the scan ends.

Common mistakesthe failure modes that look plausible in short tests