LeetCode 1249. Minimum remove to make valid parents - FB high frequency question 1

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:

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:

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

Example 3:

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

Constraints:

• 1 <= s.length <= 105
• s[i] is either'(' , ')', or lowercase English letter.

The title says that a given string contains English letters and left and right parentheses '(' and ‘)’, The left and right parentheses in the string may not match , It is required to remove the minimum number of left and right parentheses so that the rest are exactly matched , Returns a valid string after removal .

First, find out the matching principle of the left and right parentheses , When you encounter an open parenthesis , You must have a closing parenthesis after it to match , If the right bracket does not appear until the end, the left bracket is invalid and needs to be deleted ; When a closing bracket is encountered , It must be preceded by an open parenthesis waiting to match , Otherwise, the closing bracket is invalid and needs to be deleted .

thus it can be seen , The whole deletion process is based on the left parenthesis , Therefore, you can use a stack to record the left parenthesis to be matched , Scan the string from beginning to end , When you encounter an open bracket, put the open bracket on the stack （ In the stack is the position of the current left parenthesis ）; When you encounter a close bracket , Just judge whether the stack is empty at this time , If it is not empty, an open bracket will pop up from the top of the stack to match it , If it is empty, it means that the closing bracket needs to be deleted . Follow this method until the end of traversal , After that, the remaining left parentheses in the stack will also be deleted . Use one throughout the process set To record the position of the brackets to be deleted , Finally, go through it again and delete it uniformly , This will be more efficient .

class Solution:
    def minRemoveToMakeValid(self, s: str) -> str:
        rm = set()
        st = []
        for i,c in enumerate(s):
            if c == '(':
                st.append(i)
            elif c == ')':
                if not st:
                    rm.add(i)
                else:
                    st.pop()
        while st:
            rm.add(st.pop())
        res = []
        for i,c in enumerate(s):
            if i not in rm:
                res.append(c)
        
        return ''.join(res)