# lc1249. Minimum Remove to Make Valid Parentheses

Contents

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:

 ``````1 2 3 `````` ``````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:

 ``````1 2 `````` ``````Input: s = "a)b(c)d" Output: "ab(c)d" ``````

Example 3:

 ``````1 2 3 `````` ``````Input: s = "))((" Output: "" Explanation: An empty string is also valid. ``````

Constraints:

• `1 <= s.length <= 105`
• `s[i]` is either`'('` , `')'`, or lowercase English letter`.`
###### 解题思路：

 `````` 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 `````` ``````class Solution: def minRemoveToMakeValid(self, s): left, right, output = 0, s.count(')'),'' for _chr in s: if _chr=='(': if right>0: # 有效左括号 left+=1 right-=1 output+=_chr elif _chr==')': if left==0: # 无效右括号 right-=1 else: left-=1 output+=_chr else: # 非括号字符 output+=_chr return output ``````