> For the complete documentation index, see [llms.txt](https://hao-fu-1.gitbook.io/oj/llms.txt). Markdown versions of documentation pages are available by appending `.md` to page URLs; this page is available as [Markdown](https://hao-fu-1.gitbook.io/oj/exhaustive-search/remove-invalid-parentheses/remove-invalid-parentheses-return-one.md).

# 1249. Minimum Remove to Make Valid Parentheses

https\://leetcode.com/contest/weekly-contest-161/problems/minimum-remove-to-make-valid-parentheses/

> Remove the minimum number of invalid parentheses in order to make the input string valid. Return one possible results.
>
> Note: The input string may contain letters other than the parentheses`(`and`)`.

## Thoughts

由()和字母组成的字符串，返回任意一个最少删除字符能够适得()配对的结果。301的简化版, 只要返回一个不需要DFS，核心思想还是一致的。 当count < 0时意味着par\[1]数目超过par\[0], 可以删除prefix中的任意一个par\[1], 删除i。当par\[0] == '('时, 意味着多出的'('还没有删, 因此把上轮删的结果的s翻转一下, 把par\[0]换成')', 重复之前的过程。 此时s中是配好对的了, 只是顺序还是反着的, 最后再把s翻转。

## Code

```cpp
class Solution {
public:
    string minRemoveToMakeValid(string s) {
        int r = 0;
        string res;
        for (int i = 0; i < s.length(); ++i) {
            if (s[i] == '(') ++r;
            else if (s[i] == ')') --r;
            if (r >= 0) {
                res.push_back(s[i]);
            } else ++r;
        }
        s = res;
        res.clear();
        r = 0;
        for (int i = s.length() - 1; i >= 0; --i) {
            if (s[i] == ')') ++r;
            else if (s[i] == '(') --r;
            if (r >= 0) {
                res.push_back(s[i]);
            } else ++r;
        }
        reverse(res.begin(), res.end());
        return res;
    }
};
```

## Analysis

Errors:

1. 当count--到小于0时, 别忘了再把它加回去. 因为相当于删除了i, count又平衡了.

时间复杂度O(N).