# LeetCode 1021: Remove Outermost Parentheses

## Problem Restatement

A valid parentheses string is either empty, a concatenation of valid strings, or a valid string wrapped in parentheses.

A primitive valid parentheses string is one that cannot be split into two non-empty valid strings.

We are given a valid parentheses string `s`.

We need to remove the outermost parentheses of every primitive part in `s` and return the result.

The official constraints state that `1 <= s.length <= 10^5` and `s` consists of `(` and `)`.

## Input and Output

| Item | Meaning |
|---|---|
| Input | Valid parentheses string `s` |
| Output | `s` with outermost parentheses of each primitive removed |

Function shape:

```python
def removeOuterParentheses(s: str) -> str:
    ...
```

## Examples

Example 1:

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

Primitives: `"(()())"` and `"(())"`.

After removing outer: `"()()"` and `"()"`.

Answer:

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

Example 2:

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

Primitives: `"(()())"`, `"(())"`, `"(()(()))"`.

After removing outer: `"()()"`, `"()"`, `"()(())"`.

Answer:

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

Example 3:

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

Primitives: `"()"` and `"()"`.

After removing outer: `""` and `""`.

Answer:

```python
""
```

## Key Insight

Track the nesting depth as we scan the string.

A `(` at depth `0` starts a new primitive (it is the outermost `(`). Don't include it.

A `)` that brings depth back to `0` ends a primitive (it is the outermost `)`). Don't include it.

All other characters (at depth `> 0` before update) are interior and should be included.

## Algorithm

1. Initialize `depth = 0` and an empty result list.
2. For each character `c` in `s`:
   - If `c == '('`:
     - If `depth > 0`, append `c` to result (not the outermost).
     - Increment `depth`.
   - If `c == ')'`:
     - Decrement `depth`.
     - If `depth > 0`, append `c` to result (not the outermost).
3. Return the joined result.

## Correctness

Opening parentheses at depth `0` are outermost openers of primitives. By checking `depth > 0` before appending, we skip them.

Closing parentheses that bring depth to `0` are outermost closers of primitives. By checking `depth > 0` after decrement, we skip them.

All other characters are interior and correctly included.

## Edge Cases

- The stack should store exactly the unresolved items needed by the invariant.
- Process equal values deliberately; many monotonic-stack problems differ only in `<` versus `<=`.
- Flush or inspect the remaining stack after the scan if unresolved items still contribute to the answer.

## Complexity

| Metric | Value | Why |
|---|---:|---|
| Time | `O(n)` | Single pass |
| Space | `O(n)` | Result array |

## Common Pitfalls

- Do not optimize away the invariant; the code should still make it clear what condition is being maintained.
- Prefer problem-specific names over one-letter variables once the logic becomes stateful.

## Implementation

```python
class Solution:
    def removeOuterParentheses(self, s: str) -> str:
        result = []
        depth = 0

        for c in s:
            if c == '(':
                if depth > 0:
                    result.append(c)
                depth += 1
            else:
                depth -= 1
                if depth > 0:
                    result.append(c)

        return "".join(result)
```

## Code Explanation

For `(`:

```python
if depth > 0:
    result.append(c)
depth += 1
```

We append only if we are already inside a primitive (depth > 0). Then increase depth.

For `)`:

```python
depth -= 1
if depth > 0:
    result.append(c)
```

We decrease depth first. If depth is still > 0, this is an interior `)`.

## Testing

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

    assert s.removeOuterParentheses("(()())(())") == "()()()"
    assert s.removeOuterParentheses("(()())(())(()(()))") == "()()()()(())"
    assert s.removeOuterParentheses("()()") == ""
    assert s.removeOuterParentheses("((()))") == "(())"

    print("all tests passed")

run_tests()
```

| Test | Expected | Why |
|---|---|---|
| `"(()())(())"` | `"()()()"` | Two primitives stripped |
| `"(()())(())(()(()))"` | `"()()()()(())"` | Three primitives stripped |
| `"()()"` | `""` | Two trivial primitives |
| `"((()))"` | `"(())"` | Single nested primitive |