# LeetCode 32: Longest Valid Parentheses

## Problem Restatement

We are given a string `s` containing only two characters:

```python
"("
")"
```

We need to return the length of the longest valid parentheses substring.

A valid parentheses substring must be continuous, balanced, and well-formed.

Examples of valid strings:

```python
"()"
"(())"
"()()"
"(()())"
```

Examples of invalid strings:

```python
"("
")("
"(()"
"())"
```

If there is no valid parentheses substring, return `0`.

The constraints allow an empty string, and the length can be up to `3 * 10^4`. The string contains only `'('` and `')'`.

## Input and Output

| Item | Meaning |
|---|---|
| Input | A string `s` containing only `'('` and `')'` |
| Output | Length of the longest valid parentheses substring |
| Substring rule | The answer must be continuous |
| Empty string | Return `0` |
| Constraint | `0 <= s.length <= 3 * 10^4` |

Function shape:

```python
def longestValidParentheses(s: str) -> int:
    ...
```

## Examples

Example 1:

```python
s = "(()"
```

The longest valid substring is:

```python
"()"
```

Its length is:

```python
2
```

Return:

```python
2
```

Example 2:

```python
s = ")()())"
```

The longest valid substring is:

```python
"()()"
```

Its length is:

```python
4
```

Return:

```python
4
```

Example 3:

```python
s = ""
```

There are no characters, so there is no valid parentheses substring.

Return:

```python
0
```

## First Thought: Check Every Substring

A direct solution is to check every substring.

For each starting index `i`, try every ending index `j`.

For each substring `s[i:j]`, check whether it is valid.

A substring is valid when:

1. Its balance never goes below `0`.
2. Its final balance is `0`.

Here, balance means:

```python
"(" adds 1
")" subtracts 1
```

Code:

```python
class Solution:
    def longestValidParentheses(self, s: str) -> int:
        n = len(s)
        best = 0

        for left in range(n):
            balance = 0

            for right in range(left, n):
                if s[right] == "(":
                    balance += 1
                else:
                    balance -= 1

                if balance < 0:
                    break

                if balance == 0:
                    best = max(best, right - left + 1)

        return best
```

This is correct, but it is too slow for large input.

## Problem With Brute Force

There are many substrings.

For a string of length `n`, there are about:

```python
n * n
```

possible start and end pairs.

For each starting index, we may scan many characters.

With `n = 30000`, this can be far too slow.

We need a linear solution.

## Key Insight

A valid parentheses substring ends when a `")"` matches a previous `"("`.

So we need to remember the indices of unmatched opening parentheses.

A stack is a good fit.

But we also need to know where the current valid region starts.

For that, keep a base index.

The base index is the position before the current possible valid substring.

We initialize the stack with:

```python
[-1]
```

This means a valid substring starting at index `0` has length:

```python
i - (-1)
```

For example, if we reach index `1` in `"()"`, the length is:

```python
1 - (-1) = 2
```

## Algorithm

Use a stack of indices.

Initialize:

```python
stack = [-1]
best = 0
```

Then scan the string from left to right.

If the current character is `"("`, push its index.

```python
stack.append(i)
```

If the current character is `")"`:

1. Pop one index from the stack.
2. If the stack becomes empty, push the current index as the new base.
3. Otherwise, the current valid length is `i - stack[-1]`.

Why this works:

When a `")"` matches a previous `"("`, popping removes the matched opening parenthesis.

The top of the stack after popping is now the index before the current valid substring.

So the valid length is:

```python
i - stack[-1]
```

## Correctness

The stack stores indices that block or start valid substrings.

At the beginning, `-1` acts as the base before index `0`.

When we see `"("`, we push its index because it may match a future `")"`.

When we see `")"`, we pop one index. If the popped index was an opening parenthesis, then this `")"` matched it.

After the pop, if the stack still has an index, then `stack[-1]` is the position before the longest valid substring ending at the current index. Therefore, `i - stack[-1]` gives the length of that valid substring.

If the stack becomes empty, then the current `")"` has no matching `"("`. No valid substring can cross this index. We push the current index as the new base.

The algorithm checks every index once. Whenever a valid substring ends, its length is considered. Therefore, the maximum stored in `best` is the length of the longest valid parentheses substring.

## Complexity

| Metric | Value | Why |
|---|---|---|
| Time | `O(n)` | Each index is pushed and popped at most once |
| Space | `O(n)` | The stack may store many opening parentheses |

## Implementation

```python
class Solution:
    def longestValidParentheses(self, s: str) -> int:
        stack = [-1]
        best = 0

        for i, ch in enumerate(s):
            if ch == "(":
                stack.append(i)
            else:
                stack.pop()

                if not stack:
                    stack.append(i)
                else:
                    best = max(best, i - stack[-1])

        return best
```

## Code Explanation

We start with a stack containing `-1`.

```python
stack = [-1]
```

This lets us measure valid substrings that start at index `0`.

The answer starts at `0`.

```python
best = 0
```

Then we scan the string.

```python
for i, ch in enumerate(s):
```

For an opening parenthesis, push its index.

```python
if ch == "(":
    stack.append(i)
```

For a closing parenthesis, pop one index.

```python
else:
    stack.pop()
```

If the stack becomes empty, this closing parenthesis cannot be part of any valid substring crossing this index.

So we set this index as the new base.

```python
if not stack:
    stack.append(i)
```

Otherwise, the substring after `stack[-1]` up to `i` is valid.

```python
best = max(best, i - stack[-1])
```

Finally, return `best`.

## Testing

```python
def check(s: str, expected: int) -> None:
    actual = Solution().longestValidParentheses(s)
    assert actual == expected, (s, actual, expected)

def run_tests():
    check("(()", 2)
    check(")()())", 4)
    check("", 0)
    check("()", 2)
    check("()()", 4)
    check("(())", 4)
    check("())", 2)
    check("(((", 0)
    check(")))", 0)
    check("()(())", 6)
    check(")()())()()(", 4)

    print("all tests passed")

run_tests()
```

Test meaning:

| Test | Why |
|---|---|
| `"(()"` | Valid substring inside incomplete nesting |
| `")()())"` | Official style case with invalid boundaries |
| `""` | Empty input |
| `"()"` | Smallest valid string |
| `"()()"` | Adjacent valid groups |
| `"(())"` | Nested valid group |
| `"())"` | Valid prefix followed by extra close |
| `"((("` | No closing parentheses |
| `")))"` | No opening parentheses |
| `"()(())"` | Adjacent plus nested valid groups |
| `")()())()()("` | Multiple separated valid regions |