Check if a Parentheses String Can Be Valid - Solution & Explanation
Problem Statement
A parentheses string is a non-empty string consisting only of '(' and ')'. It is valid if any of the following conditions is true:
- It is
(). - It can be written as
AB(Aconcatenated withB), whereAandBare valid parentheses strings. - It can be written as
(A), whereAis a valid parentheses string.
You are given a parentheses string s and a string locked, both of length n. locked is a binary string consisting only of '0's and '1's. For each index i of locked,
- If
locked[i]is'1', you cannot changes[i]. - But if
locked[i]is'0', you can changes[i]to either'('or')'.
Return true if you can make s a valid parentheses string. Otherwise, return false.
Example 1:
Input: s = "))()))", locked = "010100"
Output: true
Explanation: locked[1] == '1' and locked[3] == '1', so we cannot change s[1] or s[3].
We change s[0] and s[4] to '(' while leaving s[2] and s[5] unchanged to make s valid.
Example 2:
Input: s = "()()", locked = "0000" Output: true Explanation: We do not need to make any changes because s is already valid.
Example 3:
Input: s = ")", locked = "0"
Output: false
Explanation: locked permits us to change s[0].
Changing s[0] to either '(' or ')' will not make s valid.
Constraints:
n == s.length == locked.length1 <= n <= 105s[i]is either'('or')'.locked[i]is either'0'or'1'.
Approach Overview
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.
Approach 1: Using Hashing for Lookup
This approach leverages a hash set or hash map to keep track of elements that have been encountered. By using these data structures, we can achieve an average time complexity of O(1) for insertions and lookups, which is useful for problems that require checking the existence of an element.
The solution uses a boolean array to simulate a hash set for integer elements, determining if the target number can be achieved as a sum of any two distinct numbers in the array. The array `hashSet` checks if the complement of the current element exists as a previously-seen number.
Complexity
Time Complexity: O(N), where N is the number of elements in the array.
Space Complexity: O(N), for the hash set used to track the elements.
Approach 2: Sorting and Two-Pointer Technique
This approach involves sorting the array and then using the two-pointer technique to find the two numbers that add up to the target. This technique is often effective when dealing with questions involving pairs, as it reduces the problem to O(N log N) due to sorting, followed by a linear scan.
By sorting the array first, we can use a two-pointer technique to efficiently find if two numbers sum up to the target. Both pointers traverse towards each other depending on the sum.
Complexity
Time Complexity: O(N log N) due to the sorting step, followed by O(N) traversal.
Space Complexity: O(1) additional space, assuming sorting is done in place.
Approach 3: Greedy + Two Passes
We observe that a string of odd length cannot be a valid parentheses string because there will always be one unmatched parenthesis. Therefore, if the length of the string s is odd, return false immediately.
Next, we perform two passes.
The first pass goes from left to right, checking if all '(' parentheses can be matched by ')' or changeable parentheses. If not, return false.
The second pass goes from right to left, checking if all ')' parentheses can be matched by '(' or changeable parentheses. If not, return false.
If both passes complete successfully, it means all parentheses can be matched, and the string s is a valid parentheses string. Return true.
The time complexity is O(n), where n is the length of the string s. The space complexity is O(1).
Similar problems:
Code
Python
Java
C++
Go
TypeScript
Complexity Comparison
| Approach | Complexity |
|---|---|
| Using Hashing for Lookup | Time Complexity: O(N), where N is the number of elements in the array. |
| Sorting and Two-Pointer Technique | Time Complexity: O(N log N) due to the sorting step, followed by O(N) traversal. |
| Greedy + Two Passes | — |
Detailed Complexity Analysis
| Approach | Time | Space | When to Use |
|---|---|---|---|
| Hashing for Lookup (tracking unlocked indices) | O(n) | O(n) | Useful when explicitly matching indices or demonstrating how flexible positions repair invalid pairs |
| Greedy Sorting / Two-Pointer Validation | O(n) | O(1) | Best general solution. Efficient for large inputs and commonly expected in interviews |
Video Solution
Check if a Parentheses String Can Be Valid - Leetcode 2116 - Python • NeetCodeIO • 18,045 views views
Watch 9 more video solutions →Frequently Asked Questions
Is Check if a Parentheses String Can Be Valid easy or hard?
Check if a Parentheses String Can Be Valid Python/Java solution
How to solve Check if a Parentheses String Can Be Valid in O(n)?
What is the best approach for Check if a Parentheses String Can Be Valid?
Is Check if a Parentheses String Can Be Valid asked at Google/Amazon/Meta?
What data structure is used in Check if a Parentheses String Can Be Valid?
What is the time complexity of Check if a Parentheses String Can Be Valid?
Ready to solve this problem?
Practice Check if a Parentheses String Can Be Valid with our built-in code editor and test cases.
Practice on FleetCode