> For the complete documentation index, see [llms.txt](https://lfool.gitbook.io/leetcodenote/llms.txt). Markdown versions of documentation pages are available by appending `.md` to page URLs; this page is available as [Markdown](https://lfool.gitbook.io/leetcodenote/30-day-leetcoding-challenge/2020-04/valid-parenthesis-string.md).

# Valid Parenthesis String

## Description

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.

**Example 1:**

> **Input:** "()" 
>
> **Output:** True

**Example 2:**

> **Input:** "(\*)" 
>
> **Output:** True

**Example 3:**

> **Input:** "(\*))" 
>
> **Output:** True

**Note:**

1. The string size will be in the range \[1, 100].

## **Code**

```java
class Solution {
    public boolean checkValidString(String s) {
        int cmin = 0;
        int cmax = 0;
        for (char c : s.toCharArray()) {
            if (c == '(') {
                cmin++;
                cmax++;
            } else if (c == ')') {
                cmin--;
                cmax--;
            } else {
                cmin--;
                cmax++;
            }
            if (cmax < 0) return false;
            cmin = Math.max(cmin, 0);
        }
        return cmin == 0;
    }
}
```