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

class Solution:
  # Same as 926. Flip String to Monotone Increasing
  def minimumDeletions(self, s: str) -> int:
    dp = 0  # the number of characters to be deleted to make subso far balanced
    count_b = 0

    for c in s:
      if c == 'a':
        # 1. Delete 'a'.
        # 2. Keep 'a' and delete the previous 'b's.
        dp = min(dp + 1, count_b)
      else:
        count_b += 1

    return dp