# LeetCode 921: Minimum Add to Make Parentheses Valid

## Problem Restatement

We are given a string `s` containing only parentheses:

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

In one move, we may insert one parenthesis at any position.

Return the minimum number of insertions needed to make the string valid.

A valid parentheses string is one where every opening parenthesis has a matching closing parenthesis in the correct order. The official statement defines the operation as inserting one parenthesis anywhere in the string.

## Input and Output

| Item | Meaning |
|---|---|
| Input | A parentheses string `s` |
| Output | Minimum number of insertions needed |
| Characters | Only `"("` and `")"` |
| Operation | Insert one parenthesis at any position |

Function shape:

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

## Examples

Example 1:

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

The first two characters form a valid pair:

```python
()
```

The final `")"` has no matching `"("`.

We need to insert one `"("`.

Answer:

```python
1
```

Example 2:

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

There are three unmatched opening parentheses.

We need three closing parentheses:

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

Answer:

```python
3
```

Example 3:

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

Process it mentally:

```python
()     matched
))     two unmatched closing parentheses
((     two unmatched opening parentheses
```

We need:

```python
2 opening parentheses + 2 closing parentheses = 4
```

Answer:

```python
4
```

## First Thought: Use a Stack

A direct way is to simulate matching parentheses with a stack.

For each character:

- If it is `"("`, push it.
- If it is `")"` and the stack has `"("`, pop one.
- Otherwise, this `")"` is unmatched and needs one inserted `"("`.

At the end, every remaining `"("` in the stack needs one inserted `")"`.

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

        for ch in s:
            if ch == "(":
                stack.append(ch)
            else:
                if stack:
                    stack.pop()
                else:
                    insertions += 1

        return insertions + len(stack)
```

This works, but the stack only stores how many unmatched opening parentheses exist.

So we can replace it with a counter.

## Key Insight

Only two values matter:

| Variable | Meaning |
|---|---|
| `open_needed` | Number of unmatched `"("` waiting for `")"` |
| `insertions` | Number of `"("` insertions needed for unmatched `")"` |

When we see `"("`, it needs a future closing parenthesis:

```python
open_needed += 1
```

When we see `")"`:

- If `open_needed > 0`, match it with one previous `"("`.
- Otherwise, this closing parenthesis has no opener, so we must insert `"("`.

After processing the whole string, any remaining `open_needed` must be closed by inserting `")"`.

## Algorithm

1. Set `open_needed = 0`.
2. Set `insertions = 0`.
3. For every character in `s`:
   - If it is `"("`, increment `open_needed`.
   - Otherwise:
     - If `open_needed > 0`, decrement `open_needed`.
     - Else, increment `insertions`.
4. Return:

```python
insertions + open_needed
```

## Correctness

When the algorithm sees `"("`, it records that this opening parenthesis still needs a matching closing parenthesis.

When it sees `")"` and `open_needed > 0`, matching it with the most recent unmatched opening parenthesis is always valid. This reduces the number of unmatched openings by one.

When it sees `")"` and `open_needed == 0`, there is no earlier opening parenthesis that can match it. The only way to make this character valid is to insert an opening parenthesis before it. So increasing `insertions` is necessary and optimal.

After the scan, every remaining unmatched `"("` needs exactly one inserted `")"`. There is no cheaper way to close them.

Thus the algorithm counts exactly the required insertions and returns the minimum.

## Complexity

| Metric | Value | Why |
|---|---:|---|
| Time | `O(n)` | We scan the string once |
| Space | `O(1)` | Only counters are used |

## Implementation

```python
class Solution:
    def minAddToMakeValid(self, s: str) -> int:
        open_needed = 0
        insertions = 0

        for ch in s:
            if ch == "(":
                open_needed += 1
            else:
                if open_needed > 0:
                    open_needed -= 1
                else:
                    insertions += 1

        return insertions + open_needed
```

## Code Explanation

Track unmatched opening parentheses:

```python
open_needed = 0
```

Track insertions needed for unmatched closing parentheses:

```python
insertions = 0
```

An opening parenthesis waits for a future close:

```python
if ch == "(":
    open_needed += 1
```

A closing parenthesis can match a previous opening parenthesis:

```python
if open_needed > 0:
    open_needed -= 1
```

If there is no previous opening parenthesis, we need to insert one:

```python
else:
    insertions += 1
```

At the end, remaining openings need closing parentheses:

```python
return insertions + open_needed
```

## Testing

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

    assert s.minAddToMakeValid("())") == 1
    assert s.minAddToMakeValid("(((") == 3
    assert s.minAddToMakeValid("()") == 0
    assert s.minAddToMakeValid("()))((") == 4
    assert s.minAddToMakeValid(")") == 1
    assert s.minAddToMakeValid("(") == 1
    assert s.minAddToMakeValid(")()(") == 2

    print("all tests passed")

run_tests()
```

Test meaning:

| Test | Why |
|---|---|
| `"())"` | One unmatched closing parenthesis |
| `"((("` | All openings need closing |
| `"()"` | Already valid |
| `"()))(("` | Both unmatched closing and opening parentheses |
| `")"` | Single unmatched closing |
| `"("` | Single unmatched opening |
| `")()("` | Unmatched characters on both ends |