# Valid Parenthesis String
**Difficulty:** MEDIUM
[External](https://leetcode.com/problems/valid-parenthesis-string)
Canonical: https://scaleengineer.com/dsa/problems/valid-parenthesis-string
**Patterns:** [Dynamic Programming](https://scaleengineer.com/dsa/patterns/dynamic-programming), [Greedy](https://scaleengineer.com/dsa/patterns/greedy)
**Data structures:** String, Stack
**Companies:** [ServiceNow](https://scaleengineer.com/companies/servicenow), [Tekion](https://scaleengineer.com/companies/tekion), [Alibaba](https://scaleengineer.com/companies/alibaba), [Roku](https://scaleengineer.com/companies/roku), [Blizzard](https://scaleengineer.com/companies/blizzard)
---
## 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 1:**

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

**Example 2:**

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

**Example 3:**

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

**Constraints:**

* `1 <= s.length <= 100`
* `s[i]` is `'('`, `')'` or `'*'`.

# Approaches
## Brute Force using Recursion
This approach explores every possible interpretation of the '*' characters. For each '*', we recursively try three possibilities: treating it as an opening parenthesis '(', a closing parenthesis ')', or an empty string. This exhaustive search checks if any combination results in a valid parenthesis string.
**Time:** O(3^n), where n is the length of the string. In the worst case (a string of all '*'), we have 3 choices for each character, leading to an exponential number of paths. · **Space:** O(n), for the recursion stack depth, where n is the length of the string.
**Pros:** Simple to understand and implement the core logic.; Correctly explores all possibilities.
**Cons:** Extremely inefficient due to its exponential time complexity.; Will result in a 'Time Limit Exceeded' error on most platforms for non-trivial inputs.
### Explanation
We define a recursive function `check(index, open_count)` which determines if the substring starting from `index` is valid, given a current balance of `open_count` open parentheses.

- The base case for the recursion is when we reach the end of the string (`index == s.length()`). The string is valid if and only if the `open_count` is zero.
- Another base case is if `open_count` ever becomes negative, which means we have an invalid sequence (e.g., a ')' without a preceding '('). In this case, we prune the search path by returning `false`.
- In the recursive step, for the character at the current `index`:
  - If it's '(', we increment `open_count` and recurse on the next index.
  - If it's ')', we decrement `open_count` and recurse.
  - If it's '*', we branch out and make three recursive calls: one for treating it as '(', one for ')', and one for an empty string. If any of these branches return `true`, the string is valid.

```java
class Solution {
    public boolean checkValidString(String s) {
        return check(s, 0, 0);
    }

    private boolean check(String s, int index, int openCount) {
        if (openCount < 0) {
            return false;
        }
        if (index == s.length()) {
            return openCount == 0;
        }

        char c = s.charAt(index);
        if (c == '(') {
            return check(s, index + 1, openCount + 1);
        } else if (c == ')') {
            return check(s, index + 1, openCount - 1);
        } else { // c == '*'
            // Try all 3 possibilities for '*'
            return check(s, index + 1, openCount + 1) || // as '('
                   check(s, index + 1, openCount - 1) || // as ')'
                   check(s, index + 1, openCount);      // as empty
        }
    }
}
```
### Algorithm
- Define a recursive function `check(s, index, openCount)`.
- `index` is the current position in the string, and `openCount` is the balance of open parentheses.
- **Base Case 1:** If `openCount` becomes negative, it's an invalid state, return `false`.
- **Base Case 2:** If `index` reaches the end of the string, the string is valid if and only if `openCount` is 0.
- **Recursive Step:**
  - If `s[index]` is `'('`, recurse with `check(s, index + 1, openCount + 1)`.
  - If `s[index]` is `')'`, recurse with `check(s, index + 1, openCount - 1)`.
  - If `s[index]` is `'*'`, explore all three possibilities by making three separate recursive calls:
    1. Treat `*` as `'('`: `check(s, index + 1, openCount + 1)`.
    2. Treat `*` as `')'`: `check(s, index + 1, openCount - 1)`.
    3. Treat `*` as empty: `check(s, index + 1, openCount)`.
  - Return `true` if any of the three branches for `*` return `true`.

## Dynamic Programming with Memoization
The brute-force recursive approach suffers from re-computing the same subproblems multiple times (e.g., arriving at the same index with the same open parenthesis count via different paths). We can optimize this by using memoization (a top-down dynamic programming technique) to store and reuse the results of subproblems.
**Time:** O(n^2), where n is the length of the string. There are `n * n` possible states for `(index, open_count)`, and each state is computed only once. · **Space:** O(n^2), for the memoization table. The recursion stack also contributes O(n), but it's dominated by the table size.
**Pros:** Significantly faster than brute force by avoiding redundant computations.; Guaranteed to pass typical constraints for this problem.
**Cons:** Uses quadratic space, O(n^2), which might be an issue for very large n.
### Explanation
We use a 2D array, `memo[index][open_count]`, to store the result of the function call `check(index, open_count)`. The state is defined by the current position in the string (`index`) and the current balance of open parentheses (`open_count`).

- Before computing the result for a state `(index, open_count)`, we first check if it's already in our `memo` table. If it is, we return the stored value immediately.
- If not, we compute the result as in the brute-force approach.
- After computing the result, we store it in `memo[index][open_count]` before returning it. This ensures that each of the O(n^2) unique subproblems is solved only once.

```java
class Solution {
    public boolean checkValidString(String s) {
        // memo[i][j] stores the result for check(s, i, j)
        // 0: not computed, 1: true, 2: false
        int[][] memo = new int[s.length()][s.length() + 1];
        return check(s, 0, 0, memo);
    }

    private boolean check(String s, int index, int openCount, int[][] memo) {
        if (openCount < 0) {
            return false;
        }
        if (index == s.length()) {
            return openCount == 0;
        }
        if (memo[index][openCount] != 0) {
            return memo[index][openCount] == 1;
        }

        boolean isValid;
        char c = s.charAt(index);
        if (c == '(') {
            isValid = check(s, index + 1, openCount + 1, memo);
        } else if (c == ')') {
            isValid = check(s, index + 1, openCount - 1, memo);
        } else { // c == '*'
            isValid = check(s, index + 1, openCount + 1, memo) || // treat as '('
                      check(s, index + 1, openCount - 1, memo) || // treat as ')'
                      check(s, index + 1, openCount, memo);      // treat as empty
        }
        
        memo[index][openCount] = isValid ? 1 : 2;
        return isValid;
    }
}
```
### Algorithm
- Use a 2D array, `memo[index][openCount]`, to store the results of subproblems. Initialize it to an 'uncomputed' state.
- The recursive function `check(s, index, openCount, memo)` is the same as the brute-force one, with two additions:
  1. **Memoization Check:** At the beginning of the function, check if `memo[index][openCount]` has already been computed. If so, return the stored result.
  2. **Store Result:** Before returning a computed result, store it in `memo[index][openCount]`.
- The state is defined by `(index, openCount)`, where `index` is the position in the string (0 to n) and `openCount` is the balance of open parentheses (0 to n).

## Using Two Stacks
This approach provides a linear time solution by using two stacks to keep track of the indices of open parentheses and asterisks. This allows us to greedily match closing parentheses and later ensure all remaining open parentheses can be closed by an asterisk that appears at a later position.
**Time:** O(n), where n is the length of the string. We perform a single pass through the string, and the final while loop also processes each element at most once. · **Space:** O(n) in the worst case, where the stacks could store up to n indices (e.g., a string of all '(' or '*')
**Pros:** Efficient linear time complexity O(n).; The logic of matching parentheses with stacks is intuitive.
**Cons:** Uses O(n) space, which is less optimal than a constant space solution.
### Explanation
We iterate through the string once, using two stacks to keep track of the positions of characters.

- We use one stack, `openStack`, to store the indices of `'('` characters.
- We use another stack, `starStack`, to store the indices of `'*'` characters.
- When we encounter a `')'` character, we try to match it. We prioritize matching with an open parenthesis, so we first try to pop from `openStack`. If it's empty, we try to pop from `starStack` (using the `'*'` as an opening parenthesis). If both stacks are empty, it's an unmatched `')'` and the string is invalid.
- After iterating through the entire string, we may have leftover `'('` in `openStack`. These must be matched by `'*'`s from `starStack`. We pop from both stacks. For a valid match, the index of the `'*'` must be greater than the index of the `'('`. This is because a `'*'` must appear after a `'('` to be able to act as its corresponding `')'`. If we find a `'('` at an index greater than a `'*'`, it's an invalid pairing.
- If `openStack` becomes empty, it means all open parentheses were successfully matched. If `openStack` is not empty but `starStack` is, we have unmatched open parentheses, and the string is invalid.

```java
import java.util.Stack;

class Solution {
    public boolean checkValidString(String s) {
        Stack<Integer> openStack = new Stack<>();
        Stack<Integer> starStack = new Stack<>();

        for (int i = 0; i < s.length(); i++) {
            char c = s.charAt(i);
            if (c == '(') {
                openStack.push(i);
            } else if (c == '*') {
                starStack.push(i);
            } else { // c == ')'
                if (!openStack.isEmpty()) {
                    openStack.pop();
                } else if (!starStack.isEmpty()) {
                    starStack.pop();
                } else {
                    return false;
                }
            }
        }

        // Match remaining open parentheses with asterisks
        while (!openStack.isEmpty() && !starStack.isEmpty()) {
            // An asterisk must appear after the open parenthesis to close it
            if (openStack.peek() > starStack.peek()) {
                return false;
            }
            openStack.pop();
            starStack.pop();
        }

        return openStack.isEmpty();
    }
}
```
### Algorithm
- Initialize two stacks: `openStack` for indices of `'('` and `starStack` for indices of `'*'`.
- Iterate through the string with index `i`:
  - If `s[i]` is `'('`, push `i` onto `openStack`.
  - If `s[i]` is `'*'`, push `i` onto `starStack`.
  - If `s[i]` is `')'`:
    - Try to pop from `openStack` first (prefer matching with a real `'('`).
    - If `openStack` is empty, pop from `starStack` (use a `'*'` as `'('`).
    - If both are empty, there's an unmatchable `')'`, so return `false`.
- After the loop, `openStack` may still contain indices of unmatched `'('`.
- While `openStack` is not empty:
  - If `starStack` is empty, there are no `'*'` left to match the `'('`, so return `false`.
  - Pop an index `openIdx` from `openStack` and `starIdx` from `starStack`.
  - A `'*'` can only act as a `')'` if it appears after the `'('`. So, if `openIdx > starIdx`, return `false`.
- If all `'('` in `openStack` are matched, return `true`.

## Greedy Approach with Range Tracking
This is the most optimal approach, achieving linear time and constant space. The core idea is to abandon tracking specific parenthesis pairings and instead maintain a range `[low, high]` representing the possible number of open parentheses needed to balance the string prefix processed so far.
**Time:** O(n), as we iterate through the string only once. · **Space:** O(1), as we only use a few variables to keep track of the counts, regardless of the input string size.
**Pros:** Most efficient solution with O(n) time and O(1) space.; Elegant and concise implementation.
**Cons:** The logic behind why the range `[low, high]` works can be less intuitive to grasp initially compared to the stack-based approach.
### Explanation
We iterate through the string and maintain two counters: `low` and `high`.
- `low`: Represents the minimum possible number of open parentheses. This is calculated by treating every `'*'` as a closing parenthesis `')'`.
- `high`: Represents the maximum possible number of open parentheses. This is calculated by treating every `'*'` as an opening parenthesis `'('`.

When we see `'('`: we increment both `low` and `high`.
When we see `')'`: we decrement both `low` and `high`.
When we see `'*'`: we decrement `low` (best case for closing) and increment `high` (best case for opening).

At each step, we must ensure two conditions:
1. `high` must never be negative. If `high < 0`, it means we have an excess of `')'` that cannot be balanced even if all preceding `'*'`s were `'('`. The string is invalid.
2. `low` should be treated as `max(low, 0)`. A negative `low` means we have more `')'` or `'*'`s (treated as `')'`) than `'('`. This is fine, as those extra closing options can be effectively absorbed by treating the `'*'`s as empty strings. We can't have a "debt" of open parentheses, so we reset the minimum required to 0.

After iterating through the entire string, the string is valid if and only if `low` is 0. A `low > 0` would mean there are unmatched open parentheses that could not be closed even when all available `'*'`s were used as `')'`.

```java
class Solution {
    public boolean checkValidString(String s) {
        int low = 0;  // Minimum number of open parentheses
        int high = 0; // Maximum number of open parentheses

        for (char c : s.toCharArray()) {
            if (c == '(') {
                low++;
                high++;
            } else if (c == ')') {
                low--;
                high--;
            } else { // c == '*'
                low--;  // '*' can be ')'
                high++; // '*' can be '('
            }

            // If at any point, the max number of open parens is negative, it's invalid.
            if (high < 0) {
                return false;
            }
            
            // The minimum number of open parens cannot be negative.
            low = Math.max(low, 0);
        }

        // At the end, the minimum number of open parens must be 0.
        return low == 0;
    }
}
```
### Algorithm
- Initialize two integer variables, `low = 0` and `high = 0`.
- `low` will track the minimum possible number of open brackets, and `high` will track the maximum.
- Iterate through each character `c` of the string:
  - If `c` is `'('`: increment both `low` and `high`.
  - If `c` is `')'`: decrement both `low` and `high`.
  - If `c` is `'*'`: decrement `low` (treating `*` as `)`) and increment `high` (treating `*` as `(`).
- After updating the counts for each character, perform two checks:
  1. If `high` becomes negative, it means there are too many closing parentheses that cannot be balanced. Return `false`.
  2. Reset `low` to `max(low, 0)`. This is because `low` represents the number of *required* open brackets, which cannot be negative. A negative value implies an excess of closing options, which we can discard by treating some `*` as empty strings.
- After the loop finishes, the string is valid if and only if `low` is 0. A non-zero `low` means there are unmatched open parentheses.

# Solutions
### Java

```java
class Solution {
public
  boolean checkValidString(String s) {
    int x = 0;
    int n = s.length();
    for (int i = 0; i < n; ++i) {
      if (s.charAt(i) != ')') {
        ++x;
      } else if (x > 0) {
        --x;
      } else {
        return false;
      }
    }
    x = 0;
    for (int i = n - 1; i >= 0; --i) {
      if (s.charAt(i) != '(') {
        ++x;
      } else if (x > 0) {
        --x;
      } else {
        return false;
      }
    }
    return true;
  }
}

```

### CPP

```cpp
class Solution {
public:
  bool checkValidString(string s) {
    int x = 0, n = s.size();
    for (int i = 0; i < n; ++i) {
      if (s[i] != ')') {
        ++x;
      } else if (x) {
        --x;
      } else {
        return false;
      }
    }
    x = 0;
    for (int i = n - 1; i >= 0; --i) {
      if (s[i] != '(') {
        ++x;
      } else if (x) {
        --x;
      } else {
        return false;
      }
    }
    return true;
  }
};

```

### Python

```python
class Solution:
    def checkValidString(self, s: str) -> bool: x = 0 for c in s: if c in '(*': x += 1 elif x: x -= 1 else: return False x = 0 for c in s[:: - 1]: if c in '*)': x += 1 elif x: x -= 1 else: return False return True

```