Valid Parenthesis String Practice

Problem Summary

You’re given a string parenthesisString containing only '(', ')', and '*'.

Rules:

Each '(' must have a matching ')' after it.
Each ')' must have a matching '(' before it.
Each '*' can be treated as:

'(', or
')', or
empty string "".

For each test case, you must determine if there exists some interpretation of '*' such that the whole string becomes a valid parenthesis string.

Input:

T test cases.
For each test case:

One string parenthesisString of length between 1 and 100.

Output:

For each test case, print true if the string can be valid, otherwise false.

Constraints:

1 <= T <= 105
1 <= |parenthesisString| <= 1001
Characters are only '(', ')', '*'.

Total characters over all test cases ≤ 107, still fine for an O(n) solution per test.

Examples Explanation

Sample Input:

()

(*)

(*))

((*))

((*)*)

Sample Output:

(Here 1 means true.)

"()"
Already a standard balanced string: valid.
"(*)"
Interpret '*' as empty:

"( )" → "()", balanced → valid.

"(*))"
Interpret '*' as '(':

"(" "(" ")" ")" → "(())", which is balanced → valid.

"((*))"
Interpret '*' as '(':

"(" "(" "(" ")" ")" → "((()))", balanced → valid.

"((*)*)" (description seems a bit informal, but idea is same)
We can choose '*' as '(' or empty appropriately to make the entire string balanced.
So it’s valid.

Approach

Pattern:

This is the classic “Valid Parenthesis String” greedy range problem.

We want to know if there exists some replacement of '*' that makes the string valid.

Naive Ideas (why they’re suboptimal):

Try all interpretations of '*'

Each '*' has 3 choices: '(', ')', or empty.
For k stars → 3k combinations → exponential and impossible.

Backtracking with pruning

Still exponential in the worst case.

We need an O(n) or O(n * T) overall approach.

Optimal Greedy Approach (Range of possible open parentheses)

The core idea: as we scan the string from left to right, we keep track of a range of how many open parentheses we might have, considering different interpretations of '*'.

Let:

low = the minimum possible number of open '(' that could be currently unmatched.
high = the maximum possible number of open '(' that could be currently unmatched.

We scan characters from left to right:

For each character c:

If c == '(':

low++ (we definitely add 1 open if we count minimally)
high++ (we also add 1 open at maximum)

If c == ')':

low-- (we close an open parenthesis in the best case)
high-- (we must close some in the worst case)

If c == '*':

low-- because '*' could act as ')', reducing open count.
high++ because '*' could act as '(', increasing open count.

Additionally:

low can never be less than 0 (we can treat extra ')' as '*' being empty or '('), so clamp:

low = max(low, 0)

If at any point high becomes negative:

This means even in the best interpretation we have more ')' than '(' → impossible → string invalid.

At the end of the string:

If low == 0, there exists an interpretation of '*' such that all opens are matched → valid.
If low > 0, we must have at least low unmatched '(' → invalid.

This correctly encapsulates all possibilities of interpreting '*'.

Pseudo-code: