Given a string s of '(' , ')' and lowercase English characters.
Your task is to remove the minimum number of parentheses ( '(' or ')', in any positions ) so that the resulting parentheses string is valid and return any valid string.
Formally, a parentheses string is valid if and only if:
AB (A concatenated with B), where A and B are valid strings, or(A), where A is a valid string.
Example 1:
Input: s = "lee(t(c)o)de)" Output: "lee(t(c)o)de" Explanation: "lee(t(co)de)" , "lee(t(c)ode)" would also be accepted.
Example 2:
Input: s = "a)b(c)d" Output: "ab(c)d"
Example 3:
Input: s = "))(("
Output: ""
Explanation: An empty string is also valid.
Constraints:
1 <= s.length <= 105s[i] is either '(' , ')', or lowercase English letter.This approach involves performing two passes over the string. In the first pass, traverse the string to identify unmatched closing parentheses and their indices. In the second pass, traverse from right to left to identify unmatched opening parentheses. This process allows removing these indices to yield a balanced parentheses string.
An array is used to filter out invalid closing parentheses on the first pass. The second pass corrects the string from the right by ignoring invalid opening parens, then reverses the string to final form.
C++
Java
Python
C#
JavaScript
Time Complexity: O(n), where n is the length of the string, since each character is visited once in each pass.
Space Complexity: O(n), as we potentially have to store the valid portion of the string.
This strategy employs a single-pass solution with a stack to track the indices of unmatched parentheses. Upon completing the pass, these tracked indices inform which characters can remain in the final valid string output. This approach saves memory by avoiding additional passes over the string.
The C implementation uses an integer stack to track the positions of parentheses. It marks invalid parentheses with a dot character and subsequently uses a secondary pass to construct the valid string.
C++
Java
Python
C#
JavaScript
Time Complexity: O(n), since each position in the strings is evaluated at most twice.
Space Complexity: O(n) for the indices stored during parentheses checking.
| Approach | Complexity |
|---|---|
| Two-Pass String Traversal with Index Tracking | Time Complexity: O(n), where n is the length of the string, since each character is visited once in each pass. |
| Single-Pass Efficient Stack Solution | Time Complexity: O(n), since each position in the strings is evaluated at most twice. |
LeetCode 1249. Minimum Remove to Make Valid Parentheses • Nick White • 34,033 views views
Watch 9 more video solutions →Practice Minimum Remove to Make Valid Parentheses with our built-in code editor and test cases.
Practice on FleetCode