678. Valid Parenthesis String - Explanation

Description

You are given a string s which contains only three types of characters: '(', ')' and '*'.

Return true if s is valid, otherwise return false.

A string is valid if it follows all of the following rules:

Every left parenthesis '(' must have a corresponding right parenthesis ')'.
Every right parenthesis ')' must have a corresponding left parenthesis '('.
Left parenthesis '(' must go before the corresponding right parenthesis ')'.
A '*' could be treated as a right parenthesis ')' character or a left parenthesis '(' character, or as an empty string "".

Example 1:

Input: s = "((**)"

Output: true

Explanation: One of the '*' could be a ')' and the other could be an empty string.

Example 2:

Input: s = "(((*)"

Output: false

Explanation: The string is not valid because there is an extra '(' at the beginning, regardless of the extra '*'.

Constraints:

1 <= s.length <= 100

Topics

Recommended Time & Space Complexity

You should aim for a solution as good or better than O(n) time and O(n) space, where n is the length of the input string.

Hint 1

A brute force approach would try all possibilities when encountering a '*' and recursively solve the problem, leading to an exponential approach. Can you think of a better way? Maybe a data structure commonly used in parenthesis problems could be useful.

Hint 2

We can solve the problem using a stack-based approach. We maintain two stacks: one for tracking the indices of left parentheses and another for star indices. As we iterate through the string from left to right, we push indices onto their respective stacks when encountering a left parenthesis '(' or a star '*'. Can you determine the logic for the right parentesis case?

Hint 3

If the left parenthesis stack is not empty, we pop from it. Otherwise, we pop from the star stack, treating the star as a left parenthesis to keep the string valid. After iterating the string, the stacks might be non-empty? Can you determine the logic for this case?

Hint 4

Now, we try to match the remaining left parentheses with stars, ensuring the stars appear after the left parentheses in the string. We simultaneously pop from both stacks, and if the index of a left parenthesis is greater than that of a star, the string is invalid as there is no matching right parenthesis. In this case, we return false.

Company Tags

Please upgrade to NeetCode Pro to view company tags.

Prerequisites

Before attempting this problem, you should be comfortable with:

Recursion - The brute force approach explores all possible interpretations using recursive backtracking
Dynamic Programming (Memoization) - Optimizing the recursive solution by caching subproblem results
Stack Data Structure - Used in one approach to track unmatched parentheses and wildcards
Greedy Algorithms - The optimal solution uses a greedy approach to track min/max possible open counts

1. Recursion

Intuition

This problem asks whether a string containing '(', ')', and '*' can be interpreted as a valid parentheses string.

The tricky part is '*', because it can represent:

'('
')'
an empty string ''

Using recursion, we try all valid interpretations of the string while keeping track of how many opening parentheses are currently unmatched.

The recursive function answers:
"Is it possible to make the substring starting at index i valid, given that we currently have open unmatched '('?"

Important rules:

The number of open parentheses (open) should never be negative
At the end of the string, all open parentheses must be closed (open == 0)

Algorithm

Define a recursive function dfs(i, open):
- i is the current index in the string
- open is the number of unmatched '(' seen so far
If open < 0:
- Too many closing parentheses, return false
If i reaches the end of the string:
- Return true only if open == 0
If s[i] == '(':
- Recurse with dfs(i + 1, open + 1)
If s[i] == ')':
- Recurse with dfs(i + 1, open - 1)
If s[i] == '*':
- Try all three possibilities:
  - treat '*' as empty → dfs(i + 1, open)
  - treat '*' as '(' → dfs(i + 1, open + 1)
  - treat '*' as ')' → dfs(i + 1, open - 1)
- If any option returns true, return true
Start the recursion with dfs(0, 0)
Return the final result

class Solution:
    def checkValidString(self, s: str) -> bool:

        def dfs(i, open):
            if open < 0:
                return False
            if i == len(s):
                return open == 0

            if s[i] == '(':
                return dfs(i + 1, open + 1)
            elif s[i] == ')':
                return dfs(i + 1, open - 1)
            else:
                return (dfs(i + 1, open) or
                        dfs(i + 1, open + 1) or
                        dfs(i + 1, open - 1))
        return dfs(0, 0)

public class Solution {
    public boolean checkValidString(String s) {

        return dfs(0, 0, s);
    }

    private boolean dfs(int i, int open, String s) {
        if (open < 0) return false;
        if (i == s.length()) return open == 0;

        if (s.charAt(i) == '(') {
            return dfs(i + 1, open + 1, s);
        } else if (s.charAt(i) == ')') {
            return dfs(i + 1, open - 1, s);
        } else {
            return dfs(i + 1, open, s) ||
                   dfs(i + 1, open + 1, s) ||
                   dfs(i + 1, open - 1, s);
        }
    }
}

class Solution {
public:
    bool checkValidString(string s) {
        return dfs(0, 0, s);
    }

private:
    bool dfs(int i, int open, const string& s) {
        if (open < 0) return false;
        if (i == s.size()) return open == 0;

        if (s[i] == '(') {
            return dfs(i + 1, open + 1, s);
        } else if (s[i] == ')') {
            return dfs(i + 1, open - 1, s);
        } else {
            return dfs(i + 1, open, s) ||
                   dfs(i + 1, open + 1, s) ||
                   dfs(i + 1, open - 1, s);
        }
    }
};

class Solution {
    /**
     * @param {string} s
     * @return {boolean}
     */
    checkValidString(s) {
        function dfs(i, open) {
            if (open < 0) return false;
            if (i === s.length) return open === 0;

            if (s[i] === '(') {
                return dfs(i + 1, open + 1);
            } else if (s[i] === ')') {
                return dfs(i + 1, open - 1);
            } else {
                return (
                    dfs(i + 1, open) ||
                    dfs(i + 1, open + 1) ||
                    dfs(i + 1, open - 1)
                );
            }
        }

        return dfs(0, 0);
    }
}

public class Solution {
    public bool CheckValidString(string s) {
        return Dfs(0, 0, s);
    }

    private bool Dfs(int i, int open, string s) {
        if (open < 0) return false;
        if (i == s.Length) return open == 0;

        if (s[i] == '(') {
            return Dfs(i + 1, open + 1, s);
        } else if (s[i] == ')') {
            return Dfs(i + 1, open - 1, s);
        } else {
            return Dfs(i + 1, open, s) ||
                   Dfs(i + 1, open + 1, s) ||
                   Dfs(i + 1, open - 1, s);
        }
    }
}

func checkValidString(s string) bool {
    var dfs func(i, open int) bool
    dfs = func(i, open int) bool {
        if open < 0 {
            return false
        }
        if i == len(s) {
            return open == 0
        }

        if s[i] == '(' {
            return dfs(i+1, open+1)
        } else if s[i] == ')' {
            return dfs(i+1, open-1)
        } else {
            return (dfs(i+1, open) ||
                    dfs(i+1, open+1) ||
                    dfs(i+1, open-1))
        }
    }
    return dfs(0, 0)
}

class Solution {
    fun checkValidString(s: String): Boolean {

        fun dfs(i: Int, open: Int): Boolean {
            if (open < 0) {
                return false
            }
            if (i == s.length) {
                return open == 0
            }

            return when (s[i]) {
                '(' -> dfs(i + 1, open + 1)
                ')' -> dfs(i + 1, open - 1)
                else -> dfs(i + 1, open) || dfs(i + 1, open + 1) || dfs(i + 1, open - 1)
            }
        }

        return dfs(0, 0)
    }
}

class Solution {
    func checkValidString(_ s: String) -> Bool {
        let chars = Array(s)

        func dfs(_ i: Int, _ open: Int) -> Bool {
            if open < 0 { return false }
            if i == chars.count { return open == 0 }

            if chars[i] == "(" {
                return dfs(i + 1, open + 1)
            } else if chars[i] == ")" {
                return dfs(i + 1, open - 1)
            } else {
                return dfs(i + 1, open) ||
                       dfs(i + 1, open + 1) ||
                       dfs(i + 1, open - 1)
            }
        }

        return dfs(0, 0)
    }
}

impl Solution {
    pub fn check_valid_string(s: String) -> bool {
        let s = s.as_bytes();

        fn dfs(s: &[u8], i: usize, open: i32) -> bool {
            if open < 0 {
                return false;
            }
            if i == s.len() {
                return open == 0;
            }
            match s[i] {
                b'(' => dfs(s, i + 1, open + 1),
                b')' => dfs(s, i + 1, open - 1),
                _ => {
                    dfs(s, i + 1, open)
                        || dfs(s, i + 1, open + 1)
                        || dfs(s, i + 1, open - 1)
                }
            }
        }

        dfs(s, 0, 0)
    }
}

Time & Space Complexity

Time complexity: $O(3 ^ n)$
Space complexity: $O(n)$

2. Dynamic Programming (Top-Down)

Intuition

We need to decide if a string containing '(', ')', and '*' can be turned into a valid parentheses string.

The character '*' is flexible and can act as:

'('
')'
empty ''

A brute-force recursion tries all possibilities, but it repeats the same work for the same positions and open counts.
To avoid that, we use top-down dynamic programming (memoization).

We track two things:

i: where we are in the string
open: how many '(' are currently unmatched

The function dfs(i, open) answers:
"Can the substring s[i:] be made valid if we currently have open unmatched opening parentheses?"

Rules:

open must never go below 0
when we reach the end, we need open == 0

Algorithm

Let n = len(s).
Create a 2D memo table memo where:
- memo[i][open] stores whether dfs(i, open) is true or false
Define a recursive function dfs(i, open):
- If open < 0, return false (too many ')')
- If i == n, return true only if open == 0
- If memo[i][open] is already computed, return it
Transition based on s[i]:
- If '(': move forward with open + 1
- If ')': move forward with open - 1
- If '*': try all three options:
  - treat as empty → dfs(i + 1, open)
  - treat as '(' → dfs(i + 1, open + 1)
  - treat as ')' → dfs(i + 1, open - 1)
  - if any option works, the result is true
Store the result in memo[i][open] and return it
Start with dfs(0, 0) and return the final answer

class Solution:
    def checkValidString(self, s: str) -> bool:
        n = len(s)
        memo = [[None] * (n + 1) for _ in range(n + 1)]

        def dfs(i, open):
            if open < 0:
                return False
            if i == n:
                return open == 0
            if memo[i][open] is not None:
                return memo[i][open]

            if s[i] == '(':
                result = dfs(i + 1, open + 1)
            elif s[i] == ')':
                result = dfs(i + 1, open - 1)
            else:
                result = (dfs(i + 1, open) or
                          dfs(i + 1, open + 1) or
                          dfs(i + 1, open - 1))

            memo[i][open] = result
            return result

        return dfs(0, 0)

public class Solution {
    public boolean checkValidString(String s) {
        int n = s.length();
        Boolean[][] memo = new Boolean[n + 1][n + 1];
        return dfs(0, 0, s, memo);
    }

    private boolean dfs(int i, int open, String s, Boolean[][] memo) {
        if (open < 0) return false;
        if (i == s.length()) return open == 0;

        if (memo[i][open] != null) return memo[i][open];

        boolean result;
        if (s.charAt(i) == '(') {
            result = dfs(i + 1, open + 1, s, memo);
        } else if (s.charAt(i) == ')') {
            result = dfs(i + 1, open - 1, s, memo);
        } else {
            result = (dfs(i + 1, open, s, memo) ||
                      dfs(i + 1, open + 1, s, memo) ||
                      dfs(i + 1, open - 1, s, memo));
        }

        memo[i][open] = result;
        return result;
    }
}

class Solution {
public:
    bool checkValidString(string s) {
        int n = s.size();
        memo = vector<vector<int>>(n + 1, vector<int>(n + 1, -1));
        return dfs(0, 0, s);
    }

private:
    vector<vector<int>> memo;

    bool dfs(int i, int open, const string& s) {
        if (open < 0) return false;
        if (i == s.size()) return open == 0;

        if (memo[i][open] != -1) return memo[i][open] == 1;

        bool result;
        if (s[i] == '(') {
            result = dfs(i + 1, open + 1, s);
        } else if (s[i] == ')') {
            result = dfs(i + 1, open - 1, s);
        } else {
            result = (dfs(i + 1, open, s) ||
                      dfs(i + 1, open + 1, s) ||
                      dfs(i + 1, open - 1, s));
        }

        memo[i][open] = result ? 1 : 0;
        return result;
    }
};

class Solution {
    /**
     * @param {string} s
     * @return {boolean}
     */
    checkValidString(s) {
        const n = s.length;
        const memo = Array.from({ length: n + 1 }, () =>
            Array(n + 1).fill(null),
        );

        function dfs(i, open) {
            if (open < 0) return false;
            if (i === n) return open === 0;

            if (memo[i][open] !== null) return memo[i][open];

            let result;
            if (s[i] === '(') {
                result = dfs(i + 1, open + 1);
            } else if (s[i] === ')') {
                result = dfs(i + 1, open - 1);
            } else {
                result =
                    dfs(i + 1, open) ||
                    dfs(i + 1, open + 1) ||
                    dfs(i + 1, open - 1);
            }

            memo[i][open] = result;
            return result;
        }

        return dfs(0, 0);
    }
}

public class Solution {
    public bool CheckValidString(string s) {
        int n = s.Length;
        bool?[,] memo = new bool?[n + 1, n + 1];
        return Dfs(0, 0, s, memo);
    }

    private bool Dfs(int i, int open, string s, bool?[,] memo) {
        if (open < 0) return false;
        if (i == s.Length) return open == 0;

        if (memo[i, open].HasValue) return memo[i, open].Value;

        bool result;
        if (s[i] == '(') {
            result = Dfs(i + 1, open + 1, s, memo);
        } else if (s[i] == ')') {
            result = Dfs(i + 1, open - 1, s, memo);
        } else {
            result = Dfs(i + 1, open, s, memo) ||
                     Dfs(i + 1, open + 1, s, memo) ||
                     Dfs(i + 1, open - 1, s, memo);
        }

        memo[i, open] = result;
        return result;
    }
}

class Solution {
    fun checkValidString(s: String): Boolean {
        val memo = Array(s.length + 1) { IntArray(s.length + 1) { -1 } }

        fun dfs(i: Int, open: Int): Boolean {
            if (open < 0) return false
            if (i == s.length) return open == 0
            if (memo[i][open] != -1) return memo[i][open] == 1

            val result = when (s[i]) {
                '(' -> dfs(i + 1, open + 1)
                ')' -> dfs(i + 1, open - 1)
                else -> (dfs(i + 1, open) ||
                         dfs(i + 1, open + 1) ||
                         dfs(i + 1, open - 1))
            }

            memo[i][open] = if (result) 1 else 0
            return result
        }

        return dfs(0, 0)
    }
}

class Solution {
    func checkValidString(_ s: String) -> Bool {
        let n = s.count
        let sArr = Array(s)
        var memo = Array(
            repeating: Array<Bool?>(repeating: nil, count: n + 1),
            count: n + 1
        )

        func dfs(_ i: Int, _ open: Int) -> Bool {
            if open < 0 {
                return false
            }
            if i == n {
                return open == 0
            }
            if let memoized = memo[i][open] {
                return memoized
            }

            let result: Bool
            if sArr[i] == "(" {
                result = dfs(i + 1, open + 1)
            } else if sArr[i] == ")" {
                result = dfs(i + 1, open - 1)
            } else {
                result = dfs(i + 1, open) ||
                         dfs(i + 1, open + 1) ||
                         dfs(i + 1, open - 1)
            }

            memo[i][open] = result
            return result
        }

        return dfs(0, 0)
    }
}

impl Solution {
    pub fn check_valid_string(s: String) -> bool {
        let s = s.as_bytes();
        let n = s.len();
        let mut memo = vec![vec![-1i8; n + 1]; n + 1];

        fn dfs(s: &[u8], i: usize, open: i32, memo: &mut Vec<Vec<i8>>) -> bool {
            if open < 0 {
                return false;
            }
            if i == s.len() {
                return open == 0;
            }
            let o = open as usize;
            if memo[i][o] != -1 {
                return memo[i][o] == 1;
            }
            let result = match s[i] {
                b'(' => dfs(s, i + 1, open + 1, memo),
                b')' => dfs(s, i + 1, open - 1, memo),
                _ => {
                    dfs(s, i + 1, open, memo)
                        || dfs(s, i + 1, open + 1, memo)
                        || dfs(s, i + 1, open - 1, memo)
                }
            };
            memo[i][o] = if result { 1 } else { 0 };
            result
        }

        dfs(s, 0, 0, &mut memo)
    }
}

Time & Space Complexity

Time complexity: $O(n ^ 2)$
Space complexity: $O(n ^ 2)$

3. Dynamic Programming (Bottom-Up)

Intuition

We need to check if a string containing '(', ')', and '*' can be interpreted as a valid parentheses string.

A helpful way to solve this is to track how many opening parentheses are currently unmatched:

open = number of '(' we still need to close

The tricky character is '*', because it can act as:

'(' (increase open)
')' (decrease open)
empty (keep open the same)

In bottom-up DP, we build answers for smaller suffixes first.

We define:

dp[i][open] = whether it is possible to make s[i:] valid if we currently have open unmatched '('

We fill this table from the end of the string back to the start.

Algorithm

Let n = len(s).
Create a 2D table dp of size (n + 1) × (n + 1) initialized to false.
Base case:
- dp[n][0] = true
  (when we are past the end of the string, it is valid only if there are no unmatched '(')
Fill the table backwards:
- iterate i from n - 1 down to 0
- iterate open from 0 up to n - 1
For each state (i, open), compute whether we can match s[i]:
- If s[i] == '*':
  - treat as '(' → check dp[i + 1][open + 1]
  - treat as ')' → check dp[i + 1][open - 1] (only if open > 0)
  - treat as empty → check dp[i + 1][open]
  - if any is true, set dp[i][open] = true
- If s[i] == '(':
  - must increase open → check dp[i + 1][open + 1]
- If s[i] == ')':
  - must decrease open → only possible if open > 0, check dp[i + 1][open - 1]
The final answer is dp[0][0]:
- starting from the beginning with 0 unmatched '('
Return dp[0][0]

class Solution:
    def checkValidString(self, s: str) -> bool:
        n = len(s)
        dp = [[False] * (n + 1) for _ in range(n + 1)]
        dp[n][0] = True

        for i in range(n - 1, -1, -1):
            for open in range(n):
                res = False
                if s[i] == '*':
                    res |= dp[i + 1][open + 1]
                    if open > 0:
                        res |= dp[i + 1][open - 1]
                    res |= dp[i + 1][open]
                else:
                    if s[i] == '(':
                        res |= dp[i + 1][open + 1]
                    elif open > 0:
                        res |= dp[i + 1][open - 1]
                dp[i][open] = res

        return dp[0][0]

public class Solution {
    public boolean checkValidString(String s) {
        int n = s.length();
        boolean[][] dp = new boolean[n + 1][n + 1];
        dp[n][0] = true;

        for (int i = n - 1; i >= 0; i--) {
            for (int open = 0; open < n; open++) {
                boolean res = false;
                if (s.charAt(i) == '*') {
                    res |= dp[i + 1][open + 1];
                    if (open > 0) res |= dp[i + 1][open - 1];
                    res |= dp[i + 1][open];
                } else {
                    if (s.charAt(i) == '(') {
                        res |= dp[i + 1][open + 1];
                    } else if (open > 0) {
                        res |= dp[i + 1][open - 1];
                    }
                }
                dp[i][open] = res;
            }
        }
        return dp[0][0];
    }
}

class Solution {
public:
    bool checkValidString(string s) {
        int n = s.size();
        vector<vector<bool>> dp(n + 1, vector<bool>(n + 1, false));
        dp[n][0] = true;

        for (int i = n - 1; i >= 0; --i) {
            for (int open = 0; open < n; ++open) {
                bool res = false;
                if (s[i] == '*') {
                    res |= dp[i + 1][open + 1];
                    if (open > 0) res |= dp[i + 1][open - 1];
                    res |= dp[i + 1][open];
                } else {
                    if (s[i] == '(') {
                        res |= dp[i + 1][open + 1];
                    } else if (open > 0) {
                        res |= dp[i + 1][open - 1];
                    }
                }
                dp[i][open] = res;
            }
        }
        return dp[0][0];
    }
};

class Solution {
    /**
     * @param {string} s
     * @return {boolean}
     */
    checkValidString(s) {
        const n = s.length;
        const dp = Array.from({ length: n + 1 }, () =>
            Array(n + 1).fill(false),
        );
        dp[n][0] = true;

        for (let i = n - 1; i >= 0; i--) {
            for (let open = 0; open < n; open++) {
                let res = false;
                if (s[i] === '*') {
                    res ||= dp[i + 1][open + 1];
                    if (open > 0) res ||= dp[i + 1][open - 1];
                    res ||= dp[i + 1][open];
                } else {
                    if (s[i] === '(') {
                        res ||= dp[i + 1][open + 1];
                    } else if (open > 0) {
                        res ||= dp[i + 1][open - 1];
                    }
                }
                dp[i][open] = res;
            }
        }
        return dp[0][0];
    }
}

public class Solution {
    public bool CheckValidString(string s) {
        int n = s.Length;
        bool[,] dp = new bool[n + 1, n + 1];
        dp[n, 0] = true;

        for (int i = n - 1; i >= 0; i--) {
            for (int open = 0; open < n; open++) {
                bool res = false;
                if (s[i] == '*') {
                    res |= dp[i + 1, open + 1];
                    if (open > 0) res |= dp[i + 1, open - 1];
                    res |= dp[i + 1, open];
                } else {
                    if (s[i] == '(') {
                        res |= dp[i + 1, open + 1];
                    } else if (open > 0) {
                        res |= dp[i + 1, open - 1];
                    }
                }
                dp[i, open] = res;
            }
        }
        return dp[0, 0];
    }
}

class Solution {
    fun checkValidString(s: String): Boolean {
        val n = s.length
        val dp = Array(n + 1) { BooleanArray(n + 1) }
        dp[n][0] = true

        for (i in n - 1 downTo 0) {
            for (open in 0 until n) {
                var res = false
                if (s[i] == '*') {
                    res = dp[i + 1][open + 1]
                    if (open > 0) {
                        res = res || dp[i + 1][open - 1]
                    }
                    res = res || dp[i + 1][open]
                } else {
                    if (s[i] == '(') {
                        res = dp[i + 1][open + 1]
                    } else if (open > 0) {
                        res = dp[i + 1][open - 1]
                    }
                }
                dp[i][open] = res
            }
        }
        return dp[0][0]
    }
}

class Solution {
    func checkValidString(_ s: String) -> Bool {
        let n = s.count
        var dp = Array(repeating: Array(repeating: false, count: n + 1), count: n + 1)
        dp[n][0] = true

        let chars = Array(s)

        for i in stride(from: n - 1, through: 0, by: -1) {
            for open in 0..<n {
                var res = false
                if chars[i] == "*" {
                    res = res || dp[i + 1][open + 1]
                    if open > 0 {
                        res = res || dp[i + 1][open - 1]
                    }
                    res = res || dp[i + 1][open]
                } else {
                    if chars[i] == "(" {
                        res = res || dp[i + 1][open + 1]
                    } else if open > 0 {
                        res = res || dp[i + 1][open - 1]
                    }
                }
                dp[i][open] = res
            }
        }

        return dp[0][0]
    }
}

impl Solution {
    pub fn check_valid_string(s: String) -> bool {
        let s = s.as_bytes();
        let n = s.len();
        let mut dp = vec![vec![false; n + 1]; n + 1];
        dp[n][0] = true;

        for i in (0..n).rev() {
            for open in 0..n {
                let mut res = false;
                if s[i] == b'*' {
                    res |= dp[i + 1][open + 1];
                    if open > 0 {
                        res |= dp[i + 1][open - 1];
                    }
                    res |= dp[i + 1][open];
                } else if s[i] == b'(' {
                    res |= dp[i + 1][open + 1];
                } else if open > 0 {
                    res |= dp[i + 1][open - 1];
                }
                dp[i][open] = res;
            }
        }
        dp[0][0]
    }
}

Time & Space Complexity

Time complexity: $O(n ^ 2)$
Space complexity: $O(n ^ 2)$

4. Dynamic Programming (Space Optimized)

Intuition

We need to check if a string containing '(', ')', and '*' can be interpreted as a valid parentheses string.

A common DP idea is to track how many opening parentheses are currently unmatched:

open = number of '(' that still need to be closed

In the 2D bottom-up DP version:

dp[i][open] told us whether s[i:] can be valid with open unmatched '('

But notice something important:

to compute values for position i, we only need values from position i + 1

So we don’t need the full 2D table. We can keep just one 1D array for the “next row” and build a new one for the “current row”.

Here:

dp[open] represents the answer for the suffix starting at i + 1
new_dp[open] represents the answer for the suffix starting at i

Algorithm

Let n = len(s).
Create a boolean array dp of size n + 1:
- dp[open] represents whether s[i+1:] can be valid with open unmatched '('
Initialize the base case (when we are past the end of the string):
- dp[0] = true (empty string is valid if open == 0)
- all other dp[open] are false
Iterate i from n - 1 down to 0:
- Create a fresh array new_dp of size n + 1 initialized to false
For each possible open from 0 to n - 1, update based on s[i]:
- If s[i] == '*', we try all three options:
  - treat as '(' → check dp[open + 1]
  - treat as ')' → check dp[open - 1] (only if open > 0)
  - treat as empty → check dp[open]
  - set new_dp[open] to true if any option works
- If s[i] == '(':
  - it increases the unmatched count → check dp[open + 1]
- If s[i] == ')':
  - it decreases the unmatched count → only possible if open > 0, check dp[open - 1]
After filling new_dp, assign dp = new_dp
The final answer is dp[0] (start from the beginning with zero unmatched '(')
Return dp[0]

class Solution:
    def checkValidString(self, s: str) -> bool:
        n = len(s)
        dp = [False] * (n + 1)
        dp[0] = True

        for i in range(n - 1, -1, -1):
            new_dp = [False] * (n + 1)
            for open in range(n):
                if s[i] == '*':
                    new_dp[open] = (dp[open + 1] or
                                    (open > 0 and dp[open - 1]) or
                                    dp[open])
                elif s[i] == '(':
                    new_dp[open] = dp[open + 1]
                elif open > 0:
                    new_dp[open] = dp[open - 1]
            dp = new_dp

        return dp[0]

public class Solution {
    public boolean checkValidString(String s) {
        int n = s.length();
        boolean[] dp = new boolean[n + 1];
        dp[0] = true;

        for (int i = n - 1; i >= 0; i--) {
            boolean[] newDp = new boolean[n + 1];
            for (int open = 0; open < n; open++) {
                if (s.charAt(i) == '*') {
                    newDp[open] = dp[open + 1] ||
                                  (open > 0 && dp[open - 1]) || dp[open];
                } else if (s.charAt(i) == '(') {
                    newDp[open] = dp[open + 1];
                } else if (open > 0) {
                    newDp[open] = dp[open - 1];
                }
            }
            dp = newDp;
        }
        return dp[0];
    }
}

class Solution {
public:
    bool checkValidString(string s) {
        int n = s.size();
        vector<bool> dp(n + 1, false);
        dp[0] = true;

        for (int i = n - 1; i >= 0; --i) {
            vector<bool> newDp(n + 1, false);
            for (int open = 0; open < n; ++open) {
                if (s[i] == '*') {
                    newDp[open] = dp[open + 1] ||
                                  (open > 0 && dp[open - 1]) || dp[open];
                } else if (s[i] == '(') {
                    newDp[open] = dp[open + 1];
                } else if (open > 0) {
                    newDp[open] = dp[open - 1];
                }
            }
            dp = newDp;
        }
        return dp[0];
    }
};

class Solution {
    /**
     * @param {string} s
     * @return {boolean}
     */
    checkValidString(s) {
        const n = s.length;
        let dp = Array(n + 1).fill(false);
        dp[0] = true;

        for (let i = n - 1; i >= 0; i--) {
            const newDp = Array(n + 1).fill(false);
            for (let open = 0; open < n; open++) {
                if (s[i] === '*') {
                    newDp[open] =
                        dp[open + 1] || (open > 0 && dp[open - 1]) || dp[open];
                } else if (s[i] === '(') {
                    newDp[open] = dp[open + 1];
                } else if (open > 0) {
                    newDp[open] = dp[open - 1];
                }
            }
            dp = newDp;
        }
        return dp[0];
    }
}

public class Solution {
    public bool CheckValidString(string s) {
        int n = s.Length;
        bool[] dp = new bool[n + 1];
        dp[0] = true;

        for (int i = n - 1; i >= 0; i--) {
            bool[] newDp = new bool[n + 1];
            for (int open = 0; open < n; open++) {
                if (s[i] == '*') {
                    newDp[open] = dp[open + 1] ||
                                  (open > 0 && dp[open - 1]) || dp[open];
                } else if (s[i] == '(') {
                    newDp[open] = dp[open + 1];
                } else if (open > 0) {
                    newDp[open] = dp[open - 1];
                }
            }
            dp = newDp;
        }
        return dp[0];
    }
}

func checkValidString(s string) bool {
    n := len(s)
    dp := make([]bool, n+1)
    dp[0] = true

    for i := n - 1; i >= 0; i-- {
        newDp := make([]bool, n+1)
        for open := 0; open < n; open++ {
            if s[i] == '*' {
                newDp[open] = (dp[open+1] ||
                               (open > 0 && dp[open-1]) ||
                               dp[open])
            } else if s[i] == '(' {
                newDp[open] = dp[open+1]
            } else if open > 0 {
                newDp[open] = dp[open-1]
            }
        }
        dp = newDp
    }
    return dp[0]
}

class Solution {
    fun checkValidString(s: String): Boolean {
        val n = s.length
        var dp = BooleanArray(n + 1)
        dp[0] = true

        for (i in n - 1 downTo 0) {
            val newDp = BooleanArray(n + 1)
            for (open in 0 until n) {
                newDp[open] = when (s[i]) {
                    '*' -> (dp[open + 1] ||
                            (open > 0 && dp[open - 1]) ||
                            dp[open])
                    '(' -> dp[open + 1]
                    else -> open > 0 && dp[open - 1]
                }
            }
            dp = newDp
        }
        return dp[0]
    }
}

class Solution {
    func checkValidString(_ s: String) -> Bool {
        let n = s.count
        var dp = Array(repeating: false, count: n + 1)
        dp[0] = true

        let chars = Array(s)

        for i in stride(from: n - 1, through: 0, by: -1) {
            var new_dp = Array(repeating: false, count: n + 1)
            for open in 0..<n {
                if chars[i] == "*" {
                    new_dp[open] = dp[open + 1] || (open > 0 && dp[open - 1]) || dp[open]
                } else if chars[i] == "(" {
                    new_dp[open] = dp[open + 1]
                } else if open > 0 {
                    new_dp[open] = dp[open - 1]
                }
            }
            dp = new_dp
        }

        return dp[0]
    }
}

impl Solution {
    pub fn check_valid_string(s: String) -> bool {
        let s = s.as_bytes();
        let n = s.len();
        let mut dp = vec![false; n + 1];
        dp[0] = true;

        for i in (0..n).rev() {
            let mut new_dp = vec![false; n + 1];
            for open in 0..n {
                new_dp[open] = match s[i] {
                    b'*' => {
                        dp[open + 1]
                            || (open > 0 && dp[open - 1])
                            || dp[open]
                    }
                    b'(' => dp[open + 1],
                    _ => open > 0 && dp[open - 1],
                };
            }
            dp = new_dp;
        }
        dp[0]
    }
}

Time & Space Complexity

Time complexity: $O(n ^ 2)$
Space complexity: $O(n)$

5. Stack

Intuition

We want to check whether a string containing '(', ')', and '*' can be interpreted as a valid parentheses string.

The character '*' is flexible and can act as:

'('
')'
or an empty string

A stack-based approach works well because:

parentheses validity depends on order
'*' can be used later to fix mismatches if needed

The key idea is to:

keep track of indices of unmatched '('
keep track of indices of '*'
use '*' as a backup when we encounter an unmatched ')'

At the end, we must also ensure that any remaining '(' can be matched with a '*' that appears after it.

Algorithm

Initialize two stacks:
- left → stores indices of '('
- star → stores indices of '*'
Traverse the string from left to right:
For each character:
- If '(':
  - push its index into left
- If '*':
  - push its index into star
- If ')':
  - If left is not empty:
    - pop one '(' from left to match this ')'
  - Else if star is not empty:
    - pop one '*' and treat it as '('
  - Else:
    - no way to match this ')', return false
After processing all characters:
- Some '(' may still be unmatched
Try to match remaining '(' with '*':
- While both stacks are non-empty:
  - pop one index from left and one from star
  - if the '(' index is greater than the '*' index:
    - '*' appears before '(' and cannot act as ')'
    - return false
If there are still unmatched '(' left:
- return false
Otherwise:
- return true

class Solution:
    def checkValidString(self, s: str) -> bool:
        left = []
        star = []
        for i, ch in enumerate(s):
            if ch == '(':
                left.append(i)
            elif ch == '*':
                star.append(i)
            else:
                if not left and not star:
                    return False
                if left:
                    left.pop()
                else:
                    star.pop()

        while left and star:
            if left.pop() > star.pop():
                return False
        return not left

public class Solution {
        public boolean checkValidString(String s) {
        Stack<Integer> left = new Stack<>();
        Stack<Integer> star = new Stack<>();
        for (int i = 0; i < s.length(); i++) {
            char ch = s.charAt(i);
            if (ch == '(') {
                left.push(i);
            } else if (ch == '*') {
                star.push(i);
            } else {
                if (left.isEmpty() && star.isEmpty()) return false;
                if (!left.isEmpty()) {
                    left.pop();
                } else{
                    star.pop();
                }
            }
        }
        while (!left.isEmpty() && !star.isEmpty()) {
            if (left.pop() > star.pop())
                return false;
        }
        return left.isEmpty();
    }
}

class Solution {
public:
    bool checkValidString(string s) {
        stack<int> left, star;
        for (int i = 0; i < s.size(); ++i) {
            if (s[i] == '(') {
                left.push(i);
            } else if (s[i] == '*') {
                star.push(i);
            } else {
                if (left.empty() && star.empty()) return false;
                if (!left.empty()) {
                    left.pop();
                } else {
                    star.pop();
                }
            }
        }

        while (!left.empty() && !star.empty()) {
            if (left.top() > star.top()) return false;
            left.pop();
            star.pop();
        }
        return left.empty();
    }
};

class Solution {
    /**
     * @param {string} s
     * @return {boolean}
     */
    checkValidString(s) {
        const left = [];
        const star = [];
        for (let i = 0; i < s.length; i++) {
            const ch = s[i];
            if (ch === '(') {
                left.push(i);
            } else if (ch === '*') {
                star.push(i);
            } else {
                if (left.length === 0 && star.length === 0) {
                    return false;
                }
                if (left.length > 0) {
                    left.pop();
                } else {
                    star.pop();
                }
            }
        }

        while (left.length > 0 && star.length > 0) {
            if (left.pop() > star.pop()) return false;
        }
        return left.length === 0;
    }
}

public class Solution {
    public bool CheckValidString(string s) {
        Stack<int> left = new Stack<int>();
        Stack<int> star = new Stack<int>();
        for (int i = 0; i < s.Length; i++) {
            char ch = s[i];
            if (ch == '(') {
                left.Push(i);
            } else if (ch == '*') {
                star.Push(i);
            } else {
                if (left.Count == 0 && star.Count == 0) return false;
                if (left.Count > 0) {
                    left.Pop();
                } else {
                    star.Pop();
                }
            }
        }

        while (left.Count > 0 && star.Count > 0) {
            if (left.Pop() > star.Pop()) return false;
        }
        return left.Count == 0;
    }
}

func checkValidString(s string) bool {
    var left, star []int
    for i, ch := range s {
        if ch == '(' {
            left = append(left, i)
        } else if ch == '*' {
            star = append(star, i)
        } else {
            if len(left) == 0 && len(star) == 0 {
                return false
            }
            if len(left) > 0 {
                left = left[:len(left)-1]
            } else {
                star = star[:len(star)-1]
            }
        }
    }

    for len(left) > 0 && len(star) > 0 {
        if left[len(left)-1] > star[len(star)-1] {
            return false
        }
        left = left[:len(left)-1]
        star = star[:len(star)-1]
    }
    return len(left) == 0
}

class Solution {
    fun checkValidString(s: String): Boolean {
        val left = ArrayDeque<Int>()
        val star = ArrayDeque<Int>()

        for ((i, ch) in s.withIndex()) {
            when (ch) {
                '(' -> left.addLast(i)
                '*' -> star.addLast(i)
                ')' -> {
                    if (left.isEmpty() && star.isEmpty()) return false
                    if (left.isNotEmpty()) left.removeLast()
                    else star.removeLast()
                }
            }
        }

        while (left.isNotEmpty() && star.isNotEmpty()) {
            if (left.last() > star.last()) return false
            left.removeLast()
            star.removeLast()
        }
        return left.isEmpty()
    }
}

class Solution {
    func checkValidString(_ s: String) -> Bool {
        var left = [Int]()
        var star = [Int]()

        let chars = Array(s)

        for (i, ch) in chars.enumerated() {
            if ch == "(" {
                left.append(i)
            } else if ch == "*" {
                star.append(i)
            } else {
                if left.isEmpty && star.isEmpty {
                    return false
                }
                if !left.isEmpty {
                    left.popLast()
                } else {
                    star.popLast()
                }
            }
        }

        while !left.isEmpty && !star.isEmpty {
            if left.last! > star.last! {
                return false
            }
            left.popLast()
            star.popLast()
        }

        return left.isEmpty
    }
}

impl Solution {
    pub fn check_valid_string(s: String) -> bool {
        let mut left = Vec::new();
        let mut star = Vec::new();

        for (i, ch) in s.bytes().enumerate() {
            match ch {
                b'(' => left.push(i),
                b'*' => star.push(i),
                _ => {
                    if left.is_empty() && star.is_empty() {
                        return false;
                    }
                    if !left.is_empty() {
                        left.pop();
                    } else {
                        star.pop();
                    }
                }
            }
        }

        while !left.is_empty() && !star.is_empty() {
            if left.pop().unwrap() > star.pop().unwrap() {
                return false;
            }
        }
        left.is_empty()
    }
}

Time & Space Complexity

Time complexity: $O(n)$
Space complexity: $O(n)$

6. Greedy

Intuition

We want to check whether a string containing '(', ')', and '*' can be interpreted as a valid parentheses string.

Instead of trying all possibilities or using stacks, we can solve this greedily by tracking a range of possible unmatched '(' counts.

Think of it this way:

At any point, we don’t need the exact number of open parentheses
We only need to know the minimum and maximum number of '(' that could be open

Why this works:

'(' always increases the number of open parentheses
')' always decreases it
'*' is flexible and can:
- decrease open count (act as ')')
- increase open count (act as '(')
- keep it unchanged (act as empty)

So we maintain:

leftMin → the minimum possible number of unmatched '('
leftMax → the maximum possible number of unmatched '('

If at any point the maximum possible opens becomes negative, the string is invalid.
At the end, if the minimum possible opens is zero, the string can be valid.

Algorithm

Initialize two counters:
- leftMin = 0
- leftMax = 0
Traverse the string character by character:
For each character c:
- If c == '(':
  - increment both leftMin and leftMax
- If c == ')':
  - decrement both leftMin and leftMax
- If c == '*':
  - treat it flexibly:
    - leftMin -= 1 (as ')')
    - leftMax += 1 (as '(')
If leftMax < 0 at any point:
- return false (too many closing parentheses)
If leftMin < 0:
- reset leftMin = 0 (we can treat extra closings as empty)
After processing the entire string:
- return true if leftMin == 0, else false

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

        for c in s:
            if c == "(":
                leftMin, leftMax = leftMin + 1, leftMax + 1
            elif c == ")":
                leftMin, leftMax = leftMin - 1, leftMax - 1
            else:
                leftMin, leftMax = leftMin - 1, leftMax + 1
            if leftMax < 0:
                return False
            if leftMin < 0:
                leftMin = 0
        return leftMin == 0

public class Solution {
    public boolean checkValidString(String s) {
        int leftMin = 0, leftMax = 0;

        for (char c : s.toCharArray()) {
            if (c == '(') {
                leftMin++;
                leftMax++;
            } else if (c == ')') {
                leftMin--;
                leftMax--;
            } else {
                leftMin--;
                leftMax++;
            }
            if (leftMax < 0) {
                return false;
            }
            if (leftMin < 0) {
                leftMin = 0;
            }
        }
        return leftMin == 0;
    }
}

class Solution {
public:
    bool checkValidString(string s) {
        int leftMin = 0, leftMax = 0;

        for (char c : s) {
            if (c == '(') {
                leftMin++;
                leftMax++;
            } else if (c == ')') {
                leftMin--;
                leftMax--;
            } else {
                leftMin--;
                leftMax++;
            }
            if (leftMax < 0) {
                return false;
            }
            if (leftMin < 0) {
                leftMin = 0;
            }
        }
        return leftMin == 0;
    }
};

class Solution {
    /**
     * @param {string} s
     * @return {boolean}
     */
    checkValidString(s) {
        let leftMin = 0;
        let leftMax = 0;

        for (const c of s) {
            if (c === '(') {
                leftMin++;
                leftMax++;
            } else if (c === ')') {
                leftMin--;
                leftMax--;
            } else {
                leftMin--;
                leftMax++;
            }
            if (leftMax < 0) {
                return false;
            }
            if (leftMin < 0) {
                leftMin = 0;
            }
        }
        return leftMin === 0;
    }
}

public class Solution {
    public bool CheckValidString(string s) {
        int leftMin = 0, leftMax = 0;

        foreach (char c in s) {
            if (c == '(') {
                leftMin++;
                leftMax++;
            } else if (c == ')') {
                leftMin--;
                leftMax--;
            } else {
                leftMin--;
                leftMax++;
            }
            if (leftMax < 0) {
                return false;
            }
            if (leftMin < 0) {
                leftMin = 0;
            }
        }
        return leftMin == 0;
    }
}

func checkValidString(s string) bool {
    leftMin, leftMax := 0, 0

    for _, c := range s {
        if c == '(' {
            leftMin, leftMax = leftMin+1, leftMax+1
        } else if c == ')' {
            leftMin, leftMax = leftMin-1, leftMax-1
        } else {
            leftMin, leftMax = leftMin-1, leftMax+1
        }
        if leftMax < 0 {
            return false
        }
        if leftMin < 0 {
            leftMin = 0
        }
    }
    return leftMin == 0
}

class Solution {
    fun checkValidString(s: String): Boolean {
        var leftMin = 0
        var leftMax = 0

        for (c in s) {
            when (c) {
                '(' -> {
                    leftMin++
                    leftMax++
                }
                ')' -> {
                    leftMin--
                    leftMax--
                }
                else -> {
                    leftMin--
                    leftMax++
                }
            }
            if (leftMax < 0) return false
            if (leftMin < 0) leftMin = 0
        }
        return leftMin == 0
    }
}

class Solution {
    func checkValidString(_ s: String) -> Bool {
        var leftMin = 0
        var leftMax = 0

        for c in s {
            if c == "(" {
                leftMin += 1
                leftMax += 1
            } else if c == ")" {
                leftMin -= 1
                leftMax -= 1
            } else {
                leftMin -= 1
                leftMax += 1
            }
            if leftMax < 0 {
                return false
            }
            if leftMin < 0 {
                leftMin = 0
            }
        }
        return leftMin == 0
    }
}

impl Solution {
    pub fn check_valid_string(s: String) -> bool {
        let (mut left_min, mut left_max) = (0i32, 0i32);

        for c in s.bytes() {
            match c {
                b'(' => {
                    left_min += 1;
                    left_max += 1;
                }
                b')' => {
                    left_min -= 1;
                    left_max -= 1;
                }
                _ => {
                    left_min -= 1;
                    left_max += 1;
                }
            }
            if left_max < 0 {
                return false;
            }
            if left_min < 0 {
                left_min = 0;
            }
        }
        left_min == 0
    }
}

Time & Space Complexity

Time complexity: $O(n)$
Space complexity: $O(1)$

Common Pitfalls

Forgetting That Wildcards Have Three Options

A common mistake is treating '*' as only representing '(' or ')'. Remember that '*' can also represent an empty string. This third option is crucial for cases like "(*)" where the '*' should be treated as empty to form a valid string.

Not Checking for Negative Open Count

When processing ')' or treating '*' as ')', you must ensure the open parenthesis count never goes negative. A negative count means there are more closing parentheses than opening ones at that point, which is invalid regardless of what comes later. Always check open >= 0 before proceeding.

Ignoring the Position of Wildcards in Stack Approach

In the stack-based solution, simply counting unmatched '(' and '*' is not enough. You must also verify that each remaining '(' has a '*' that appears after it (at a higher index). A '*' appearing before a '(' cannot act as a matching ')' for it.