1249. Minimum Remove to Make Valid Parentheses
https://leetcode.com/problems/minimum-remove-to-make-valid-parentheses/
---
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:
- It is the empty string, contains only lowercase characters, or
- It can be written as
AB(Aconcatenated withB), whereAandBare valid strings, or - It can be written as
(A), whereAis 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.
Example 4:
Input: s = "(a(b(c)d)" Output: "a(b(c)d)"
Constraints:
1 <= s.length <= 10^5s[i]is one of'(',')'and lowercase English letters.
---
Intuition
--
Can be solved with one stack tracking the unbalanced parenthesis index
---
Also possible with two data structures
Can be solved with one stack tracking the unbalanced parenthesis index
---
Also possible with two data structures
Track the mismatched open and closed parenthesis separately.
Extra open can be tracked with a stack of open parenthesis
Extra closed can be tracked in a set
Work through the string backwards since stack is LIFO
--
Time - O(n)
Space - O(n)
Related problems
1021-remove-outermost-parentheses
---
