A parentheses string is considered valid if it satisfies any of the following conditions:

• It is the empty string.

• It can be written as $AB$, which is the concatenation of $A$ and $B$, where both $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 binary string locked, both of length n. A character locked[i] indicates whether s[i] can be modified:

• If locked[i] is '1', you cannot alter s[i].

• If locked[i] is '0', you can change s[i] to either '(' or ')'.

Return true if it is possible to make s a valid parentheses string, or false otherwise.

Constraints:

• n $=$ s.length $=$ locked.length

• $1 \leq$ n $\leq 10^5$

• s[i] is either '(' or ')'.

• locked[i] is either '0' or '1'.

Now, let’s take a moment to make sure you’ve correctly understood the problem. The quiz below helps you check if you’re solving the correct problem:

We have a game for you to play. Rearrange the logical building blocks to develop a clearer understanding of how to solve this problem.

Implement your solution in the following coding playground.