Check if a Parentheses String Can Be Valid - Solution & Explanation

Problem Overview: You receive a parentheses string s and a binary string locked. If locked[i] = 1, the character at s[i] cannot change. If locked[i] = 0, you may flip it between ( and ). The task is to determine whether the string can be transformed into a valid parentheses sequence.

A quick observation: a valid parentheses string must have even length. If n is odd, the answer is immediately false.

Approach 1: Using Hashing for Lookup (Greedy Balance Tracking) (O(n) time, O(n) space)

This approach tracks locked and unlocked positions while scanning the string. Use a hash-based structure (such as sets or maps) to record indices of flexible characters (locked[i] = 0) and unmatched parentheses. While iterating through the string, treat unlocked characters as potential fixes for imbalance. When you encounter an extra closing parenthesis, look up a previously stored unlocked index and convert it to an opening parenthesis. If no such index exists, the sequence cannot be fixed. A second pass ensures remaining unmatched openings can be balanced by later unlocked positions. The hash lookup provides constant-time checks for available replacements.

This strategy models the problem as flexible corrections in the sequence. It’s helpful when reasoning about which indices can be swapped or reassigned dynamically. It also makes the matching process explicit by storing candidate positions.

Approach 2: Sorting and Two-Pointer Technique (Greedy Range Validation) (O(n) time, O(1) space)

The optimal approach treats unlocked characters as wildcards and validates feasibility using two directional passes. Scan from left to right while maintaining a balance counter. Treat unlocked characters as ( if needed to prevent the balance from dropping below zero. This ensures you never have more closing parentheses than possible openings.

Next, run a reverse scan (right to left). This time treat unlocked characters as ) when necessary to ensure the suffix can be balanced. Conceptually, this works like a two-pointer validation across the string: the forward pass guarantees prefixes are fixable, and the backward pass guarantees suffixes are fixable.

The key insight is that unlocked characters can be assigned optimally depending on which direction you scan. No explicit stack is required; simple counters track the feasible range of open parentheses. This greedy method runs in linear time and constant space, which is ideal for large inputs.

Problems like this commonly appear in discussions about string processing, stack-based validation, and greedy algorithms. Understanding how flexible characters affect balance constraints is the main trick.

Recommended for interviews: The greedy two-pass approach is what interviewers typically expect. It demonstrates you understand the structural property of valid parentheses and can reason about constraints without brute-force search. A hash-based or stack-style solution shows the matching intuition, but the O(n) time and O(1) space greedy validation signals stronger algorithmic thinking.