LeetCode · #678

Valid Parenthesis String Solution

Given a string with (, ), and * (wildcard: empty, (, or )), determine if the string can be valid.

Section One · Problem

Problem Statement

🏷️

Difficulty

Medium

🔗

LeetCode

Problem #678

🏗️

Pattern

Greedy — min/max open count

Each * can be (, ), or empty string. Return true if the string can be made valid as parentheses.

Example

Input: s = "(*)" Output: true // * can be empty → "()" is valid Input: s = "(*))" Output: true // * can be "(" → "(())" is valid

Constraints

• 1 ≤ s.length ≤ 100 • s[i] is '(', ')' or '*'

Section Two · Approach 1

Brute Force — O(3ⁿ)

For each *, try all three options. Check if any assignment yields a valid string.

Problem: Exponential. Instead of tracking exact open count, track the range of possible open counts. If the range includes 0 at the end, it's valid.

Java — Recursive

 class Solution {
public boolean checkValidString(String s) {
return check(s, 0, 0);
    }
private boolean check(String s, int i, int open) {
if (open < 0) return false;
if (i == s.length()) return open == 0;
if (s.charAt(i) == '(') return check(s, i+1, open+1);
if (s.charAt(i) == ')') return check(s, i+1, open-1);
return check(s,i+1,open+1) || check(s,i+1,open-1) || check(s,i+1,open);
    }
}

Python — Recursive

 class Solution:
def checkValidString(self, s: str) -> bool:
def check(i, o):
if o < 0: return False if i == len(s): return o == 0 if s[i] == '(': return check(i+1, o+1)
if s[i] == ')': return check(i+1, o-1)
return check(i+1,o+1) or check(i+1,o-1) or check(i+1,o)
return check(0, 0)

Section Three · Approach 2

Greedy Min/Max — O(n) time, O(1) space

Track lo (minimum possible open parens) and hi (maximum possible open parens). ( increments both. ) decrements both. * decrements lo, increments hi. Clamp lo at 0. If hi < 0, impossible.

💡 Mental model: Imagine balancing a scale where ( adds weight (open count) and ) removes it. A * is a wildcard weight — it could add, remove, or do nothing. Instead of tracking every possibility, track the range [lo, hi] of possible scale readings. If the range ever excludes 0 entirely (hi < 0), it's impossible. If the range includes 0 at the end (lo ≤ 0 ≤ hi, which means lo == 0 since we clamp), it's valid.

Algorithm

lo = 0, hi = 0.
For each char: ( → lo++, hi++. ) → lo--, hi--. * → lo--, hi++.
If hi < 0: too many ), return false.
Clamp lo = max(lo, 0) (can't have negative open parens).
Return lo == 0.

🎯 When to recognize this pattern: "Parentheses validation with wildcards." The signal: characters that can be multiple things + validity check. Min/max range tracking collapses exponential branching into a linear sweep. Also useful for fuzzy matching scenarios.

Section Four · Trace

Visual Walkthrough

Trace for s = "(*))".

Valid Parenthesis String — Min/Max Tracking

Section Five · Implementation

Code — Java & Python

Java — Greedy min/max

 class Solution {
public boolean checkValidString(String s) {
int lo = 0, hi = 0;
for (char c : s.toCharArray()) {
            lo += c == '(' ? 1 : -1;
            hi += c != ')' ? 1 : -1;
if (hi < 0) return false; // too many )
lo = Math.max(lo, 0);
        }
return lo == 0;
    }
}

Python — Greedy min/max

 class Solution:
def checkValidString(self, s: str) -> bool:
        lo = hi = 0 for c in s:
            lo += 1 if c == '(' else -1
hi += 1 if c != ')' else -1 if hi < 0: return False
lo = max(lo, 0)
return lo == 0

Section Six · Analysis

Complexity Analysis

Approach	Time	Space	Trade-off
Brute force	O(3ⁿ)	O(n)	Try all * assignments
DP with memo	O(n²)	O(n²)	Memoize (index, openCount)
Greedy min/max ← optimal	O(n)	O(1)	Two variables track range of possibilities

Section Seven · Edge Cases

Edge Cases & Pitfalls

Case	Input	Why It Matters
All stars	`"***"`	All can be empty. lo=0. Valid.
Star as close	`"(*"`	* = ) → "()". Valid. lo=0, hi=2 → clamp lo=0.
Too many closes	`")("`	hi goes negative at first char. Return false.
No stars	`"(())"`	Standard parentheses. lo tracks normally.
Unmatched opens	`"((("`	lo=3 at end ≠ 0. Return false.

⚠ Common Mistake: Only tracking hi (maximum possible open count) and checking hi >= 0. This misses cases where lo > 0 at the end — meaning even in the best case, there are unmatched open parens. You need both lo and hi: lo for "can we match all opens?" and hi for "did we ever have too many closes?"

← Back to Greedy problems

LearningTree

LC 678 · Valid Parenthesis String — Solution & Explanation | DSA Guide