LeetCode 678 - Valid Parenthesis String

Difficulty: 🟡 Medium
Topics: String, Dynamic Programming, Stack, Greedy

Solution

Problem Understanding

This problem is asking whether a string containing the characters '(', ')', and '*' can be considered a valid parenthesis string. In essence, '(' must be matched by a ')' in the correct order, and '*' can act as a flexible placeholder that behaves as '(', ')', or an empty string. The input s is a string with length between 1 and 100, so it is relatively small, which allows some flexibility in approach selection. The expected output is a boolean value, true if the string can be made valid by interpreting '*' appropriately, and false otherwise.

Key edge cases include strings composed entirely of '*', strings that start with ')' or end with '(', and combinations where multiple '*' characters could either resolve or break balance depending on their interpretation. The constraints guarantee that the input will only include '(', ')', or '*', so we do not need to validate input characters.

Approaches

A brute-force approach would be to generate all possible replacements of '*' with '(', ')', or an empty string and then check whether each resulting string is valid. This works because it exhaustively tests all interpretations, but it is extremely inefficient. For a string of length n with k '*' characters, there are 3^k possible strings to check, which becomes unmanageable even for moderate n.

The key insight for a better solution is that we do not need to generate all combinations. Instead, we can track the range of possible open parentheses as we traverse the string. We maintain a low and high counter: low represents the minimum possible number of unmatched '(' (treating '*' as ')'), and high represents the maximum possible number of unmatched '(' (treating '*' as '('). If high drops below 0 at any point, there are too many ')' characters and the string is invalid. If low reaches 0, it is clamped at 0 since negative open counts are impossible. At the end, if low is 0, the string is valid.

Approach	Time Complexity	Space Complexity	Notes
Brute Force	O(3^k * n)	O(n)	Generate all possible strings by replacing `'*'` and check each for validity
Optimal (Greedy)	O(n)	O(1)	Track range of unmatched `'('` using `low` and `high` counters, single pass

Algorithm Walkthrough

Initialize two counters, low and high, to 0. These represent the minimum and maximum number of unmatched '(' respectively.
Iterate over each character c in the string s.
If c is '(', increment both low and high by 1 since it increases the count of unmatched open parentheses.
If c is ')', decrement both low and high by 1 since it closes a parenthesis. Clamp low to 0 because we cannot have negative unmatched '('.
If c is '*', treat it as either '(', ')', or empty. Increment high by 1 (consider '*' as '(') and decrement low by 1 (consider '*' as ')') and clamp low to 0.
If at any point high becomes negative, return false immediately since it indicates too many unmatched ')'.
After processing all characters, return true if low is 0, indicating that there exists an interpretation where all parentheses are matched; otherwise, return false.

Why it works: The low and high counters maintain a feasible range of unmatched '(' at each step. If this range ever becomes invalid (high < 0), no valid interpretation exists. If the lower bound low reaches 0 by the end, there is a valid interpretation that balances all parentheses.

Python Solution

class Solution:
    def checkValidString(self, s: str) -> bool:
        low = 0
        high = 0
        
        for c in s:
            if c == '(':
                low += 1
                high += 1
            elif c == ')':
                low = max(low - 1, 0)
                high -= 1
            else:  # c == '*'
                low = max(low - 1, 0)
                high += 1
                
            if high < 0:
                return False
        
        return low == 0

The code uses low and high counters to track the minimum and maximum number of unmatched '(' at each character. '(' increments both, ')' decrements both with low clamped to 0, and '*' adjusts the range to account for its three possible interpretations. If high drops below 0, the function immediately returns False, otherwise it returns True if low is 0 at the end.

Go Solution

func checkValidString(s string) bool {
    low, high := 0, 0
    
    for _, c := range s {
        switch c {
        case '(':
            low++
            high++
        case ')':
            if low > 0 {
                low--
            }
            high--
        case '*':
            if low > 0 {
                low--
            }
            high++
        }
        if high < 0 {
            return false
        }
    }
    
    return low == 0
}

In Go, we use integer variables low and high for the same purpose. The switch statement is used for clarity. low is clamped using if low > 0 { low-- }. The rest of the logic mirrors the Python implementation. No dynamic memory structures are needed, making this efficient in both space and time.

Worked Examples

Example 1: s = "()"

Step	Char	low	high
1	'('	1	1
2	')'	0	0

low is 0 at the end, return True.

Example 2: s = "(*)"

Step	Char	low	high
1	'('	1	1
2	'*'	0	2
3	')'	0	1

low is 0 at the end, return True.

Example 3: s = "(*))"

Step	Char	low	high
1	'('	1	1
2	'*'	0	2
3	')'	0	1
4	')'	0	0

low is 0 at the end, return True.

Complexity Analysis

Measure	Complexity	Explanation
Time	O(n)	Single pass through the string, n = length of s
Space	O(1)	Only two integer counters are used

The algorithm scales linearly with input size. There is no additional memory allocated that grows with n, making it very efficient for the problem constraints.

Test Cases

# Provided examples
assert Solution().checkValidString("()") == True  # simple valid pair
assert Solution().checkValidString("(*)") == True  # '*' as ')'
assert Solution().checkValidString("(*))") == True  # '*' as '('

# Edge and boundary cases
assert Solution().checkValidString("*") == True  # '*' as empty
assert Solution().checkValidString("**") == True  # multiple '*' as empty
assert Solution().checkValidString(")(") == False  # impossible to balance
assert Solution().checkValidString("(((*)") == False  # unmatched '('
assert Solution().checkValidString("(*)*") == True  # '*' can balance remaining '('
assert Solution().checkValidString("") == True  # empty string

# Longer complex case
assert Solution().checkValidString("((*))((*))(**)") == True  # complex nested with multiple '*'

Test	Why
"()"	basic valid case
"(*)"	'*' balances as ')'
"(*))"	'*' balances as '('
"*"	'*' as empty string
"**"	multiple '*' as empty or balanced parentheses
")("	cannot be valid
"(((*)"	unmatched '('
"()"	'*' used to balance remaining '('
""	empty string valid by definition
"(())(())(**)"	complex nested structure with multiple '*'

Edge Cases

One important edge case is a string starting with ')'. A naive implementation might not detect early that the string is invalid. The greedy approach correctly sets high to -1, immediately returning False.

A second edge case is a string with only '*'. The algorithm must handle this without assuming any fixed interpretation. Clamping low to 0 ensures that the range remains valid regardless of how