> For the complete documentation index, see [llms.txt](https://adit0503.gitbook.io/leetcode/llms.txt). Markdown versions of documentation pages are available by appending `.md` to page URLs; this page is available as [Markdown](https://adit0503.gitbook.io/leetcode/678.-valid-parenthesis-string.md).

# 678. Valid Parenthesis String

Medium

Given a string containing only three types of characters: '(', ')' and '\*', write a function to check whether this string is valid. We define the validity of a string by these rules:\
1\. Any left parenthesis '(' must have a corresponding right parenthesis ')'.\
2\. Any right parenthesis ')' must have a corresponding left parenthesis '('.\
3\. Left parenthesis '(' must go before the corresponding right parenthesis ')'.\
4\. '\*' could be treated as a single right parenthesis ')' or a single left parenthesis '(' or an empty string.\
5\. An empty string is also valid.

## :innocent: [Solution](https://leetcode.com/problems/valid-parenthesis-string/)

{% tabs %}
{% tab title="O(n)" %}

```python
class Solution:
    def checkValidString(self, s: str) -> bool:
        cmin = cmax = 0
        for i in s:
            cmax = cmax - 1 if i == ')' else cmax + 1
            cmin = cmin + 1 if i == '(' else max(cmin - 1, 0)
            if cmax < 0: return False
        return cmin == 0
```

{% endtab %}
{% endtabs %}