1249. Minimum Remove to Make Valid Parentheses

https://leetcode.com/problems/minimum-remove-to-make-valid-parentheses/

solution

class Solution:
    def minRemoveToMakeValid(self, s: str) -> str:
        s = list(s)  # 一定要先展开, 否则下面直接把位置变为空则s是动态的

        stack = []  # 栈只负责左右括号，删除调整的动作是在s的list上
        for i, char in enumerate(s):
            if char == '(':
                stack.append(i)  # 注意index入栈，用index调整字符串位置
            elif char == ')':
                if stack:
                    stack.pop()  # stack里只有左括号
                else:
                    s[i] = ''  # 多余的右括号去掉. 因此一开始要变为list，才可以按序号修改

        while stack:  # 注意是while
            s[stack.pop()] = ''  # 多余的左括号去掉
        return ''.join(s)

时间复杂度：O(n) 空间复杂度：O(n)

follow up

括号类小结

301 Remove Invalid Parentheses

1653. Minimum Deletions to Make String Balanced