A parentheses string is a non-empty string consisting only of '(' and ')'. It is valid if any of the following conditions is true:
().AB (A concatenated with B), where A and B are valid parentheses strings.(A), where A is 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,
locked[i] is '1', you cannot change s[i].locked[i] is '0', you can change s[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'.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.
C++
Java
Python
C#
JavaScript
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.
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.
C++
Java
Python
C#
JavaScript
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 | 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. |
Valid Parenthesis String - Leetcode 678 - Python • NeetCode • 85,490 views views
Watch 9 more video solutions →Practice Check if a Parentheses String Can Be Valid with our built-in code editor and test cases.
Practice on FleetCodePractice this problem
Open in Editor