# 資訊

:::info
- Question: 1249. Minimum Remove to Make Valid Parentheses
- From: Leetcode Daily Challenge 2024.04.06
- Difficulty: Medium
:::

---

# 目錄

:::info
[TOC]
:::

---

# 題目

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:
:::success
* 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:
:::success
* Input: `s = "a)b(c)d"`
* Output: `"ab(c)d"`
:::

> Example 3:
:::success
* Input: `s = "))(("`
* Output: `""`
* Explanation: An empty string is also valid.
:::

> Constraints:
:::success
* 1 <= `s.length` <= $10^5$
* `s[i]` is either `'('` , `')'`, or lowercase English letter.
:::

---

# 解法

## 概念

有酷的題目，這題的解法一樣是拿 stack 解決，把需要移除掉的括號移掉就好，但對於佐括號和右括號的移法判斷剛好會相反，所以需要從左到右移除右括號，再由右到左移除左括號，這樣才能把全部不合法的括號移除

兩個小細節注意：
1. 由右到左移除時 for loop 的順序要注意
2. 最後解答要記得 reverse 再回傳

詳細可以看 code 的 comment，註解寫得很詳細！

## 程式碼

class Solution:
    def minRemoveToMakeValid(self, s: str) -> str:
        stack = []
        ans = []
        
        # From left to right
        for i in range(len(s)):
            if s[i] == '(':
                stack.append('(')
                ans.append('(')
            elif s[i] == ')':
                if stack and stack[-1] == '(':  # if not stack -> ')' is illegal and thus remove
                    stack = stack[:-1]
                    ans.append(')')
            else:   # lower case English letter
                ans.append(s[i])
        
        # Transform ans from list to string
        s = ''.join(ans)
        stack = []
        ans = []

        # From right to left
        for i in range(len(s)-1,-1,-1):
            if s[i] == ')':
                stack.append(')')
                ans.append(')')
            elif s[i] == '(':
                if stack and stack[-1] == ')':  # if not stack -> ')' is illegal and thus remove
                    stack = stack[:-1]
                    ans.append('(')
            else:   # lower case English letter
                ans.append(s[i])
        
        return ''.join(ans)[::-1]

---

# 複雜度

## 時間複雜度

時間最主要就是 traverse 兩次字串，所以是 $O(n)$。不過說 $O(n)$，那個係數也是有點大，像我的應該至少超過 5，這也是複雜度爛成這樣的關係吧！有機會做成 inline 的會更好！


## 空間複雜度

空間部分存了兩次答案的 list 和 stack，所以會是 $O(n)$