> For the complete documentation index, see [llms.txt](https://www.vjssn.dev/llms.txt). Markdown versions of documentation pages are available by appending `.md` to page URLs; this page is available as [Markdown](https://www.vjssn.dev/practice/24-06-13/lc678-valid-parenthesis-string.md).

# LC678 - Valid Parenthesis String

## Problem

Given a string `s` containing only three types of characters: `'('`, `')'` and `'*'`, return `true` *if* `s` *is **valid***.

The following rules define a **valid** string:

* Any left parenthesis `'('` must have a corresponding right parenthesis `')'`.
* Any right parenthesis `')'` must have a corresponding left parenthesis `'('`.
* Left parenthesis `'('` must go before the corresponding right parenthesis `')'`.
* `'*'` could be treated as a single right parenthesis `')'` or a single left parenthesis `'('` or an empty string `""`.

### Example

**Input:** s = "()"

**Output:** true

## Solution

### Greedy

Seems to be a parsing problem, solvable in $$O(n)$$ with no extra space used.

```python
def checkValidString(self, s: str) -> bool:
	leftMin = 0
	leftMax = 0

	
	for char in s:
		if char == '(':
			leftMin += 1
			leftMax += 1
		elif char == ')':
			leftMin -= 1
			leftMax -= 1
		# char is **
		else: 
			leftMin -= 1
			leftMax += 1

		# Reset to 0 because wilds can be left unused
		if leftMin < 0:
			leftMin = 0

		# more rights than left + wild
		if leftMax < 0:
			return False

	# True unless left > right
	if leftMin == 0:
		return True
		
	return False
	
```