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

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.

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)

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)

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]

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]

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

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

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.