# LeetCode 678: Valid Parenthesis String

## Problem Restatement

We are given a string `s`.

The string contains only three characters:

| Character | Meaning |
|---|---|
| `'('` | Opening parenthesis |
| `')'` | Closing parenthesis |
| `'*'` | Wildcard character |

The wildcard `'*'` can be treated as one of three choices:

| Choice | Meaning |
|---|---|
| `'('` | Use it as an opening parenthesis |
| `')'` | Use it as a closing parenthesis |
| empty string | Remove it |

We need to return `true` if there is some way to replace every `'*'` so that the final string is a valid parenthesis string. Otherwise, return `false`.

A valid parenthesis string must satisfy the usual rules: every opening parenthesis must be matched by a later closing parenthesis, and every closing parenthesis must match an earlier opening parenthesis. The official problem defines `'*'` with these three possible meanings.

## Input and Output

| Item | Meaning |
|---|---|
| Input | A string `s` containing only `'('`, `')'`, and `'*'` |
| Output | `true` if the string can be valid, otherwise `false` |

Example function shape:

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

## Examples

Example 1:

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

This is already valid.

Answer:

```python
True
```

Example 2:

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

We can treat `'*'` as empty.

Then the string becomes:

```text
()
```

Answer:

```python
True
```

Example 3:

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

We can treat `'*'` as `'('`.

Then the string becomes:

```text
(())
```

Answer:

```python
True
```

Example 4:

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

The first character is `')'`.

There is no earlier `'('` that can match it.

Answer:

```python
False
```

## First Thought: Try Every Replacement

A direct approach is to try every possible meaning of each `'*'`.

For each `'*'`, we branch into three choices:

```text
'*' -> '('
'*' -> ')'
'*' -> empty
```

After trying a replacement, we check whether the resulting parenthesis string is valid.

This works logically, but if there are many stars, the number of possibilities grows very quickly.

If there are `k` stars, there are:

```text
3^k
```

possible replacements.

That is too expensive.

## Key Insight

For ordinary parentheses, we can scan left to right and keep a count of unmatched opening parentheses.

For this problem, `'*'` makes the count uncertain.

Instead of keeping one count, we keep a range of possible counts.

Let:

| Variable | Meaning |
|---|---|
| `low` | Minimum possible number of unmatched `'('` |
| `high` | Maximum possible number of unmatched `'('` |

After scanning part of the string, the actual number of unmatched opening parentheses could be any value between `low` and `high`.

The range changes like this:

| Character | Effect |
|---|---|
| `'('` | Both `low` and `high` increase |
| `')'` | Both `low` and `high` decrease |
| `'*'` | It can be `')'`, empty, or `'('`, so `low` decreases and `high` increases |

But `low` cannot go below `0`.

A negative number of unmatched opening parentheses does not make sense. If `low` becomes negative, we clamp it back to `0`.

If `high` becomes negative, then even the most generous interpretation cannot provide enough opening parentheses. At that point, the string is impossible.

## Algorithm

Initialize:

```python
low = 0
high = 0
```

Then scan each character `ch` in `s`.

If `ch == '('`:

```python
low += 1
high += 1
```

Both the minimum and maximum number of unmatched opens increase.

If `ch == ')'`:

```python
low -= 1
high -= 1
```

A closing parenthesis must consume one unmatched open.

If `ch == '*'`:

```python
low -= 1
high += 1
```

The minimum decreases because `'*'` may act as `')'`.

The maximum increases because `'*'` may act as `'('`.

After each character:

```python
if high < 0:
    return False

low = max(low, 0)
```

At the end, the string is valid if `0` is one possible unmatched-open count.

That means:

```python
low == 0
```

## Walkthrough

Consider:

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

Start:

| Step | Character | `low` | `high` | Meaning |
|---:|---|---:|---:|---|
| 0 | none | 0 | 0 | No unmatched opens |
| 1 | `'('` | 1 | 1 | Must have one open |
| 2 | `'*'` | 0 | 2 | Star can close, vanish, or open |
| 3 | `')'` | 0 | 1 | One closing parenthesis used |
| 4 | `')'` | 0 | 0 | All opens can be matched |

At the end, `low == 0`, so the answer is `true`.

Now consider:

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

Start:

| Step | Character | `low` | `high` | Meaning |
|---:|---|---:|---:|---|
| 0 | none | 0 | 0 | No unmatched opens |
| 1 | `')'` | 0 | -1 | Impossible |

`high < 0`, so there is no way to match the first closing parenthesis.

Return `false`.

## Correctness

The algorithm maintains this invariant after each scanned prefix:

`low` is the smallest possible number of unmatched opening parentheses, and `high` is the largest possible number of unmatched opening parentheses, over all valid interpretations of `'*'` in that prefix.

At the start, before scanning anything, the only possible count is `0`, so `low = high = 0`.

When the next character is `'('`, every possible interpretation gains one unmatched opening parenthesis. Therefore both bounds increase by one.

When the next character is `')'`, every possible interpretation must use one unmatched opening parenthesis. Therefore both bounds decrease by one. If `high` becomes negative, then even the largest possible number of opens was not enough, so no interpretation can be valid.

When the next character is `'*'`, it may act as `')'`, empty, or `'('`. These choices can decrease the unmatched-open count by one, keep it unchanged, or increase it by one. Therefore the minimum possible count decreases by one, and the maximum possible count increases by one.

Because the number of unmatched opening parentheses cannot be negative, clamping `low` to `0` preserves the smallest meaningful possible count.

After the full string is scanned, the string can be valid exactly when zero unmatched opening parentheses is possible.

That is exactly the condition `low == 0`.

Therefore, the algorithm returns `true` if and only if the string can be interpreted as a valid parenthesis string.

## Complexity

Let `n` be the length of `s`.

| Metric | Value | Why |
|---|---:|---|
| Time | `O(n)` | We scan the string once |
| Space | `O(1)` | We only store two counters |

## Implementation

```python
class Solution:
    def checkValidString(self, s: str) -> bool:
        low = 0
        high = 0

        for ch in s:
            if ch == "(":
                low += 1
                high += 1
            elif ch == ")":
                low -= 1
                high -= 1
            else:
                low -= 1
                high += 1

            if high < 0:
                return False

            low = max(low, 0)

        return low == 0
```

## Code Explanation

We start with:

```python
low = 0
high = 0
```

These variables describe the possible range of unmatched opening parentheses.

For `'('`, both counters increase:

```python
low += 1
high += 1
```

There is no choice here. An opening parenthesis always adds one unmatched open.

For `')'`, both counters decrease:

```python
low -= 1
high -= 1
```

A closing parenthesis must match a previous opening parenthesis.

For `'*'`, the range expands:

```python
low -= 1
high += 1
```

The lowest case treats `'*'` as `')'`.

The highest case treats `'*'` as `'('`.

Then we check:

```python
if high < 0:
    return False
```

If `high` is negative, every possible interpretation has too many closing parentheses.

Finally:

```python
low = max(low, 0)
```

This removes impossible negative lower bounds.

At the end:

```python
return low == 0
```

If `low` is zero, then zero unmatched opening parentheses is possible, so the string can be valid.

## Testing

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

    assert s.checkValidString("()") is True
    assert s.checkValidString("(*)") is True
    assert s.checkValidString("(*))") is True
    assert s.checkValidString(")*(") is False

    assert s.checkValidString("*") is True
    assert s.checkValidString("(") is False
    assert s.checkValidString(")") is False

    assert s.checkValidString("((*)") is True
    assert s.checkValidString("(((******))") is True
    assert s.checkValidString("(((((*)))") is True
    assert s.checkValidString("(((((") is False

    print("all tests passed")

run_tests()
```

Test meaning:

| Test | Expected | Why |
|---|---:|---|
| `"()"` | `true` | Already valid |
| `"(*)"` | `true` | Star can be empty |
| `"(*))"` | `true` | Star can be `'('` |
| `")*("` | `false` | Starts with unmatched closing parenthesis |
| `"*"` | `true` | Star can be empty |
| `"("` | `false` | One unmatched opening parenthesis |
| `")"` | `false` | One unmatched closing parenthesis |
| `"((*)"` | `true` | Star can be `')'` |
| `"(((******))"` | `true` | Stars can balance extra opens |
| `"(((((*)))"` | `true` | One star can close one extra open |
| `"((((("` | `false` | No closings or stars to balance opens |