LeetEye LeetEye
Medium Greedy ~5 min

Valid Parenthesis String

greedy valid-parenthesis-string

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

Examples

Example 1
Input: s = "()"
Output: true
Example 2
Input: s = "(*)"
Output: true
Example 3
Input: s = "(*))"
Output: true
Key Insight

Track range of possible open parentheses counts [low, high].

Track [low, high] range of possible open counts. '(' increases both, ')' decreases both, '*' does both. If high < 0, fail. At end, low must be 0.

How to Approach This Problem

Pattern Recognition: When you see keywords like valid parenthesis string greedy, think Greedy.

Step-by-Step Reasoning

1 We track a range [low, high] because:
Answer: * can be (, ), or empty → multiple possibilities
At any point, open count could be anywhere in a range depending on * choices.
2 When we see '(':
Answer: low++, high++
'(' definitely adds one open parenthesis.
3 When we see ')':
Answer: low--, high--
')' definitely closes one parenthesis.
4 When we see '*':
Answer: low--, high++
* as ')' decreases open count (low--), * as '(' increases it (high++).
5 String is valid if:
Answer: A and C
If high < 0, too many ')'. At end, low must be 0 (all opens matched).

Solution

def checkValidString(s: str) -> bool:
    low = 0   # Minimum possible open count
    high = 0  # Maximum possible open count
    
    for c in s:
        if c == &#039;(':
            low += 1
            high += 1
        elif c == &#039;)':
            low -= 1
            high -= 1
        else:  # '*'
            low -= 1   # Treat as ')'
            high += 1  # Treat as '('
        
        # Too many closing parens
        if high < 0:
            return False
        
        # low can't go negative (we'd just treat * as empty)
        low = max(low, 0)
    
    return low == 0

Complexity Analysis

Time O(n)
Space O(1)

Master This Pattern

Build intuition with interactive MCQs. Practice Greedy problems in the LeetEye app.

Download LeetEye Free
Practice in LeetEye