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?(A?concatenated with?B), where?A?and?B?are valid strings, or - It can be written as?
(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.
题目说给定一个字符串包含英文字母和左右小括号'('和‘)’，字符串里的左右小括号有可能是不匹配的，要求移除最少个数的左右小括号使得剩下的是完全匹配的，返回移除后的有效字符串。
首先要搞清楚左右小括号的匹配原则，当遇到一个左括号时，后面必须要有一个右括号才能匹配，要是直到最后也没出现右括号则该左括号为无效需被删除；当遇到一个右括号时，其前面必须要有一个等着匹配的左括号，否则该右括号为无效需要被删除。
由此可见，整个删除过程是基于左括号的，因此可以用一个堆栈来记录待匹配的左括号，从头到尾扫一遍字符串，当遇到左括号就把左括号放入堆栈里（堆栈里放的是当前左括号的位置）；当遇到右括号时，就判断此时堆栈是否为空，如不为空则从堆栈顶弹出一个左括号与其匹配，如为空表示该右括号需要被删除。按此方法直到遍历结束，结束后堆栈里剩下的左括号也都是要被删除的。在整个过程中用一个set来记录要被删除的括号的位置，最后再遍历一遍统一删除，这样效率会比较高。
class Solution:
def minRemoveToMakeValid(self, s: str) -> str:
rm = set()
st = []
for i,c in enumerate(s):
if c == '(':
st.append(i)
elif c == ')':
if not st:
rm.add(i)
else:
st.pop()
while st:
rm.add(st.pop())
res = []
for i,c in enumerate(s):
if i not in rm:
res.append(c)
return ''.join(res)
