1249.Minimum_Remove_to_Make_Valid_Parentheses(Medium).md

1249. Minimum Remove to Make Valid Parentheses (Medium)

Date and Time: Nov 22, 2024, 10:40 (EST)

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

Question:

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 <= 10^5

• s[i] is either '(' , ')', or lowercase English letter.

Walk-through:

1. We first convert string into list, so we can access each char by its index.

2. When we encounter "(", we save its index into a stack[].

3. When we encounter ")", we first check if stack[] is empty or not. If stack is empty, we just change ")" to be "", because it doesn't make sense to have a closing parenthese before we have a opening parenthese. If we have index of open parenthese in stack[], we should pop the last element from stack to "close up" a parenthese "()".

4. Lastly, we check if we have remaining open parenthese "(" in stack. If so, we change each of them to be "" to remove the extra "(".

5. Finally, we convert the list back to string.

Python Solution:

class Solution:
    def minRemoveToMakeValid(self, s: str) -> str:s
        # Convert s into list
        # save the index of "(" into stack
        # when we encounter ")", if stack is not empty, pop the last index from stack so we can close this parenthese. Otherwise, we change the ")" to be empty ""
        # For the rest of "(" indices in stack, replace them with ""
        # Finally, join list(s) = str(s)

        # TC: O(n), n = len(s), SC: O(n)
        s = list(s)
        stack = []
        for i, c in enumerate(s):
            if c == '(':
                stack.append(i)
            elif c == ')':
                # If stack is not empty, close up parenthese
                if stack:
                    stack.pop()
                # Otherwise, just set ")" to be empty
                else:
                    s[i] = ""
        # Remove the rest "(" from stack[] by setting it to be ""
        while stack:
            s[stack.pop()] = ""
        return "".join(s)

Time Complexity: $O(n)$
Space Complexity: $O(n)$