# Parentheses

## 20. Valid Parentheses

```python
def isValid(self, s: str) -> bool:
    dic = {')':'(', ']':'[', '}':'{'}
    stack = []
    
    for c in s:
        if c in dic:
            left = '#' if not stack else stack.pop()
            if left != dic[c]:
                return False
        else:
            stack.append(c)
            
    return not stack
```

## 678. Valid Parenthesis String

Given a string containing only three types of characters: '(', ')' and '\*', write a function to check whether this string is valid. We define the validity of a string by these rules:

1. Any left parenthesis `'('` must have a corresponding right parenthesis `')'`.
2. Any right parenthesis `')'` must have a corresponding left parenthesis `'('`.
3. Left parenthesis `'('` must go before the corresponding right parenthesis `')'`.
4. `'*'` could be treated as a single right parenthesis `')'` or a single left parenthesis `'('` or an empty string.
5. An empty string is also valid

```python
 """
Count the lower bound and higher bound of left bracket
If higher bound < 0, means it can't be valid in current position and afterward
Check if lower bound == 0 when return
"""
def checkValidString(self, s: str) -> bool:
    lo, hi = 0, 0
    
    for c in s:
        lo += 1 if c == '(' else -1
        hi += 1 if c in '(*' else -1
        if hi < 0: return False
        if lo < 0: lo = 0
            
    return lo == 0
```

## 22. Generate Parentheses

Given n pairs of parentheses, write a function to generate all combinations of well-formed parentheses.

```python
n = 3
[
  "((()))",
  "(()())",
  "(())()",
  "()(())",
  "()()()"
]
```

```python
 def generateParenthesis(self, n: int) -> List[str]:
    ans = []
    
    def backtracking(s, left, right):
        if len(s) == 2*n:
            ans.append(s)
            return
        if left < n:
            backtracking(s+'(', left+1, right)
        if right < left:
            backtracking(s+')', left, right+1)
            
    backtracking('', 0, 0)
    
    return ans         
```

## 32. Longest Valid Parentheses

Given a string containing just the characters `'('` and `')'`, find the length of the longest valid (well-formed) parentheses substring.

dp

1. State: dp\[i], s\[:i+1]的LVP
2. Tran: only consider s\[i] == ')', \
   dp\[i] = dp\[i-2] + 2 if s\[i-1] == '('\
   dp\[i] = dp\[i-dp\[i-1]-1] + 2 if s\[i-1] = ')'\
   &#x20;        \+ dp\[i-dp\[i-1]-2] if i-dp\[i-1]-2 >= 0&#x20;

```python
def longestValidParentheses(self, s: str) -> int:    
    dp = [0] * len(s)
    ans = 0

    for i in range(1, len(s)):
        if s[i] == ')':
            if s[i-1] == '(':
                dp[i] = 2 + (dp[i-2] if i-2 >= 0 else 0)
            elif i-dp[i-1]-1 >= 0 and s[i-dp[i-1]-1] == '(':
                dp[i] = 2 + dp[i-1]
                if i-dp[i-1]-2 >= 0:
                    dp[i] += dp[i-dp[i-1]-2]

        ans = max(ans, dp[i])
    return ans
```

List double end traverse

There are only three cases for a string:

1. '(' are more than ')'
2. '(' are less than ')'
3. '(' and ')' are the same

Now, when you scan from left to right, you can only find the correct `maxLength` for cases 2 and 3, because if it is case 1, where '(' are more than ')' (e.g., `"((()"`), then `left` is always greater than `right` and `maxLength` does not have the chance to be updated.

```python
 def longestValidParentheses(self, s: str) -> int: 
    left, right = 0, 0 ans = 0
    for c in s:
        if c == '(': left+=1
        else: right+=1

        if left == right:
            ans = max(ans, right*2)
        elif right > left:
            left, right = 0, 0


    left, right = 0, 0
    for c in s[::-1]:
        if c == '(': left+=1
        else: right+=1

        if left == right:
            ans = max(ans, right*2)
        elif left > right:
            left, right = 0, 0

    return ans
```

## 1190. Reverse Substrings Between Each Pair of Parentheses

You are given a string `s` that consists of lower case English letters and brackets. Reverse the strings in each pair of matching parentheses, starting from the innermost one.

```python
Input: s = "(abcd)"
Output: "dcba"
```

Time: O(n^2), Space: O(n)

```python
def reverseParentheses(self, s: str) -> str:
    line = ''
    stack = []
    
    for c in s:
        if c == '(':
            stack.append(line)
            line = ''
        elif c == ')':
            pre = stack.pop()
            pre += line[::-1]
            line = pre
        else:
            line += c
            
    return line
```

Time: O(n) for 2 passes, see [Lee's explanation](https://leetcode.com/problems/reverse-substrings-between-each-pair-of-parentheses/discuss/383670/JavaC%2B%2BPython-Why-not-O\(N\))

## 921. Minimum Add to Make Parentheses Valid

Given a string `S` of `'('` and `')'` parentheses, we add the minimum number of parentheses ( `'('` or `')'`, and in any positions ) so that the resulting parentheses string is valid.

```python
def minAddToMakeValid(self, S: str) -> int:
    balance = 0
    count = 0

    for c in S:
        balance += 1 if c == '(' else -1

        # right bracket is greater, must add a left bracket
        if balance == -1:
            count += 1
            balance = 0
                  # rest of left brackets
    return count + balance
```

## 1249. Minimum Remove to Make Valid Parentheses

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.

```python
  """
  record the index should be removed and rebuild the string
  """
  def minRemoveToMakeValid(self, s: str) -> str:
    stack = [] # record left parentheses to remove
    remove = set() # record right parenthesese to remove
    
    for i, c in enumerate(s):
        if c not in '()': continue
        if c == '(':
            stack.append(i)
        # "))((" 的情況
        elif c == ')' and not stack:
            remove.add(i)
        else:
            stack.pop()
            
    remove = remove.union(set(stack))
    
    build = ''
    for i in range(len(s)):
        if i not in remove:
            build += s[i]
            
    return build
```

## 301. Remove Invalid Parentheses

example

```
Input: "()())()"
Output: ["()()()", "(())()"]
```

1. 先計算 需要remove 多少 '(' and ')'
2. Backtracking, 適當剪支, 符合條件加入答案(利用set, 因為可能重複)

```python
def removeInvalidParentheses(self, s: str) -> List[str]:
    # count invalid '(' and ')'

    left, right = 0, 0
    for c in s:
        if c == '(':
            left += 1
        elif c == ')':
            if left == 0:
                right += 1
            else:
                left -= 1

    self.ans = set()
    self.dfs(s, 0, 0, 0, left, right, '')
    return list(self.ans)


def dfs(self, s, idx, l, r, left_rem, right_rem, exp):
    if idx == len(s):
        if left_rem == right_rem == 0:
            self.ans.add(exp)
        return

    c = s[idx]
    #  ignore c either keep c 分開討論
    if c == '(':
        self.dfs(s, idx+1, l+1, r, left_rem, right_rem, exp+c)
        if left_rem > 0:
            self.dfs(s, idx+1, l, r, left_rem-1, right_rem, exp)
    elif c == ')':
        # prune, 只有 r < l 才進行 recursion
        if l > r:
            self.dfs(s, idx+1, l, r+1, left_rem, right_rem, exp+c)
        if right_rem > 0:
            self.dfs(s, idx+1, l, r, left_rem, right_rem-1, exp)
    # c is letter        
    else:
        self.dfs(s, idx+1, l, r, left_rem, right_rem, exp+c)
```

##


---

# Agent Instructions: Querying This Documentation

If you need additional information that is not directly available in this page, you can query the documentation dynamically by asking a question.

Perform an HTTP GET request on the current page URL with the `ask` query parameter:

```
GET https://netjimmy.gitbook.io/code-interview-note/2.1-string/parentheses.md?ask=<question>
```

The question should be specific, self-contained, and written in natural language.
The response will contain a direct answer to the question and relevant excerpts and sources from the documentation.

Use this mechanism when the answer is not explicitly present in the current page, you need clarification or additional context, or you want to retrieve related documentation sections.