# Valid Parenthesis String

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].

## Solution

### Code Explanation

1. Declare two stacks, one for storing the indexes of open brackets and another for storing indexes of star(*).
2. First thing, we want to balance close brackets.
3. Remember star can be act as empty character or open bracket or close bracket based on the requirement.
4. In the first phase, consider star will act as open bracket.
5. Whenever you get close bracket ‘)’, check open bracket is empty or not, if it is not empty pop from it. Otherwise check star is empty or not, if it is not empty pop from it. If both of them are empty, then return false.
6. Once you done that, then we want to balance for open brackets.
7. Now star will act as close bracket or empty to balance the open brackets.
8. Look at the solution, for deep understanding.

C# Program

```public class Solution {
public bool CheckValidString(string s) {

Stack<int> open = new Stack<int>();

Stack<int> star = new Stack<int>();

//Balancing for close bracket
for(int i=0;i<s.Length;i++){
if(s[i] == '(')
open.Push(i);
else if(s[i] == '*')
star.Push(i);
else{
if(open.Count > 0)
open.Pop();
else if(star.Count > 0)
star.Pop();
else
return false;
}
}

//Balancing for open bracket
while(open.Count > 0){
int openIndex = open.Pop();
if(star.Count > 0)
{
int starIndex = star.Pop();
if(openIndex > starIndex)
return false;
}
else
return false;
}
return open.Count == 0;

}
}```

Time Complexity: O(n)

Space Complexity: O(n)