Check if a Parentheses String Can Be Valid

Check if a Parentheses String Can Be Valid

What is this problem about?

The "Check if a Parentheses String Can Be Valid interview question" is a flexible string challenge. You are given a parentheses string and a "locked" string of the same length (0s and 1s). A '1' in the locked string means the character at that index cannot be changed. A '0' means you can change that character to either '(' or ')'. You need to determine if it's possible to make the entire string a valid parentheses sequence.

Why is this asked in interviews?

Companies like Meta and Google ask the "Check if a Parentheses String Can Be Valid coding problem" to test a candidate's ability to handle Greedy balancing and Stack concepts with uncertainty. It requires more than just a simple balance count; you must account for the "wildcard" potential of the unlocked characters. It’s an advanced "String interview pattern" problem.

Algorithmic pattern used

This problem is solved using a Two-Pass Greedy or Min-Max Range pattern.

1. Odd Length Check: If the string length is odd, it can never be valid. Return false immediately.
2. Forward Pass (Left to Right): Ensure we don't have too many closing parentheses. Count "openable" characters (unlocked characters + fixed '('). If the count of ')' exceeds this, it's impossible.
3. Backward Pass (Right to Left): Ensure we don't have too many opening parentheses. Count "closable" characters (unlocked characters + fixed ')'). If the count of '(' exceeds this, it's impossible.
4. Alternative: Maintain a range [min_open, max_open] representing the possible number of open parentheses after each character and ensure the range always includes 0 at the end and never goes negative.

Example explanation

String: "))((", Locked: "0000"

• Both passes: Everything is unlocked, so we can change the first two to (( and the last two to )). Result: True. String: "()()", Locked: "1111"
• Already valid and locked. Result: True. String: ")", Locked: "1"
• Odd length. Result: False.

Common mistakes candidates make

• Only one pass: Only checking for closing brackets from the left. You also need to ensure there aren't excess opening brackets that cannot be closed.
• Ignoring the Locked status: Treating all characters as changeable.
• Complex DP: Attempting a $O(N^2)$ dynamic programming approach when a $O(N)$ greedy pass is sufficient.

Interview preparation tip

For parentheses problems, always think about "Balance." Usually, a single counter is enough for simple cases, but when flexibility is added, a two-pass approach or tracking a range of possible balances is the standard "String interview pattern."