# LeetCode 20: Valid Parentheses

## Problem Restatement

We are given a string `s` containing only these six bracket characters:

```text
( ) { } [ ]
```

We need to determine whether the bracket string is valid.

A string is valid when:

1. Every opening bracket is closed by the same type of bracket.
2. Opening brackets are closed in the correct order.
3. Every closing bracket has a matching opening bracket of the same type.

For example:

```text
"()[]{}"
```

is valid.

But:

```text
"([)]"
```

is invalid, because `[` is opened after `(`, so `]` must close before `)`. The source statement defines exactly these bracket types and validity rules.

## Input and Output

| Item | Meaning |
|---|---|
| Input | A string `s` containing only bracket characters |
| Output | `true` if the string is valid, otherwise `false` |
| Bracket types | `()`, `{}`, `[]` |
| Valid order | The most recently opened bracket must close first |

Example function shape:

```python
def isValid(s: str) -> bool:
    ...
```

## Examples

Example 1:

```text
s = "()"
```

The opening bracket `(` is closed by `)`.

Output:

```text
true
```

Example 2:

```text
s = "()[]{}"
```

Each pair is complete and correctly ordered.

Output:

```text
true
```

Example 3:

```text
s = "(]"
```

The opening bracket `(` cannot be closed by `]`.

Output:

```text
false
```

Example 4:

```text
s = "([)]"
```

The brackets are closed in the wrong order.

Output:

```text
false
```

Example 5:

```text
s = "{[]}"
```

The inner `[]` closes first, then the outer `{}` closes.

Output:

```text
true
```

## First Thought: Count Brackets

One tempting idea is to count each bracket type.

For example, count how many `(` and `)` appear.

But counts alone are not enough.

Consider:

```text
"([)]"
```

The counts are balanced:

| Bracket | Count |
|---|---:|
| `(` | 1 |
| `)` | 1 |
| `[` | 1 |
| `]` | 1 |

But the string is still invalid because the closing order is wrong.

We need to track nesting order, not only counts.

## Key Insight

Brackets follow a last-opened, first-closed rule.

For example:

```text
{ [ ( ) ] }
```

The most recent opening bracket is `(`, so it must be closed by `)` before `[` or `{` can close.

This is exactly the behavior of a stack.

A stack lets us:

- push opening brackets
- pop the most recent opening bracket when we see a closing bracket
- check whether the popped bracket matches the closing bracket

## Visual Walkthrough

Use:

```text
s = "{[]}"
```

Start with an empty stack.

Read `{`:

```text
stack = ["{"]
```

Read `[`:

```text
stack = ["{", "["]
```

Read `]`.

The top of the stack is `[`.

It matches `]`, so pop it:

```text
stack = ["{"]
```

Read `}`.

The top of the stack is `{`.

It matches `}`, so pop it:

```text
stack = []
```

The string is finished and the stack is empty.

So the string is valid.

Now compare:

```text
s = "([)]"
```

Read `(`:

```text
stack = ["("]
```

Read `[`:

```text
stack = ["(", "["]
```

Read `)`.

The top of the stack is `[`, but `)` needs `(`.

Mismatch.

Return `false`.

## Algorithm

1. Create an empty stack.
2. Create a map from closing bracket to matching opening bracket.
3. Scan each character in `s`.
4. If the character is an opening bracket, push it.
5. If the character is a closing bracket:
   - if the stack is empty, return `false`
   - pop the top opening bracket
   - if it does not match, return `false`
6. After scanning all characters, return whether the stack is empty.

## Correctness

The stack stores opening brackets that have not been closed yet.

Its top is always the most recently opened unmatched bracket.

When the algorithm sees a closing bracket, the only bracket that may legally match it is the top of the stack. If the stack is empty, there is no opening bracket for this closing bracket. If the top has a different type, the closing order or bracket type is invalid.

If the top matches, popping it correctly marks that pair as closed.

After all characters are processed, any remaining opening bracket in the stack has no matching closing bracket. So the string is valid exactly when the stack is empty.

Therefore the algorithm returns `true` exactly for valid bracket strings.

## Complexity

| Metric | Value | Why |
|---|---|---|
| Time | `O(n)` | Each character is processed once |
| Space | `O(n)` | The stack may store all opening brackets |

## Implementation

```python
class Solution:
    def isValid(self, s: str) -> bool:
        pairs = {
            ")": "(",
            "}": "{",
            "]": "[",
        }

        stack = []

        for char in s:
            if char in pairs:
                if not stack:
                    return False

                top = stack.pop()

                if top != pairs[char]:
                    return False
            else:
                stack.append(char)

        return len(stack) == 0
```

## Code Explanation

The map stores the required opening bracket for each closing bracket:

```python
pairs = {
    ")": "(",
    "}": "{",
    "]": "[",
}
```

The stack stores unmatched opening brackets:

```python
stack = []
```

When `char` is a closing bracket:

```python
if char in pairs:
```

we need a previous opening bracket.

If the stack is empty:

```python
if not stack:
    return False
```

then this closing bracket has nothing to close.

Otherwise, pop the most recent opening bracket:

```python
top = stack.pop()
```

Check whether it matches:

```python
if top != pairs[char]:
    return False
```

If `char` is not a closing bracket, it must be an opening bracket, so push it:

```python
stack.append(char)
```

At the end:

```python
return len(stack) == 0
```

The stack must be empty for all brackets to be closed.

## Testing

```python
def run_tests():
    s = Solution()

    assert s.isValid("()") is True
    assert s.isValid("()[]{}") is True
    assert s.isValid("(]") is False
    assert s.isValid("([)]") is False
    assert s.isValid("{[]}") is True
    assert s.isValid("]") is False
    assert s.isValid("((") is False
    assert s.isValid("([]{})") is True

    print("all tests passed")

run_tests()
```

| Test | Why |
|---|---|
| `"()"` | Single valid pair |
| `"()[]{}"` | Multiple adjacent valid pairs |
| `"(]"` | Wrong bracket type |
| `"([)]"` | Wrong closing order |
| `"{[]}"` | Nested valid brackets |
| `"]"` | Closing bracket without opener |
| `"(("` | Unclosed opening brackets |
| `"([]{})"` | Mixed nesting and adjacency |