# 1249. Minimum Remove to Make Valid Parentheses

{% embed url="<https://leetcode.com/problems/minimum-remove-to-make-valid-parentheses/>" %}

题目给的`s`长度在10^5，时间复杂度只能是O(n\*logn)以下，遍历最多一次，直接用 Q301 的 backtracking 会TLE（即便根据当前string长度进行剪枝），所有基于树搜索的方法都应该可以排除了。

换一个办法追踪括号的开闭状态，参考 Q20，用 `stack` 记录左括号，遇到右括号就对对碰。或者一开始就把`s`转为 list，这样可以一边遍历一边生成结果字符的列表，也不需要再用`stack`记录多余左括号的具体位置，只要记录个数，最后从尾往头删就行了。

{% content-ref url="20.-valid-parentheses" %}
[20.-valid-parentheses](https://xuqiangwen1994.gitbook.io/practice/20.-valid-parentheses)
{% endcontent-ref %}

{% tabs %}
{% tab title="stack" %}

```python
class Solution:
    def minRemoveToMakeValid(self, s: str) -> str:
        stack, redundant = [], set()
        i = 0
        for i, c in enumerate(s):
            if c == '(':
                stack.append(i)
            elif c == ')':
                if stack:
                    stack.pop()
                else:
                    redundant.add(i)
        return "".join([s[i] for i in range(len(s)) if i not in stack and i not in redundant])
```

{% endtab %}
{% endtabs %}
