AlgoViz
HomeGreedy

Valid Paranthesis Checker

Hard

Track a range of possible open counts

Problem

A string has '(' , ')' and '*' (which is '(' , ')' or empty). Return true if it can be a valid parenthesis string.

In simple words

Track the possible range of open brackets; '*' widens it, and validity holds if 0 stays reachable.

The idea

A '*' can be an opener, a closer, or nothing, so instead of one counter carry the minimum and maximum number of unmatched openers. The string is valid if the maximum never goes negative and the minimum can reach zero at the end.

The trick

  • '*' increases the maximum and decreases the minimum.
  • Clamp the minimum at zero — it can never be negative in reality.
  • Fail immediately if the maximum drops below zero.

This one walks through the worked example rather than tracing the algorithm frame by frame — a full walkthrough is still to be drawn. The code and the idea below are the real solution.

0
0

Step 1 of 2. Here's the example — (*)) Values: 0.

1/2
Optimal
timeO(n)spaceO(1)
1lo=hi=02for c in s:3  if c=='(' : lo++, hi++4  elif c==')': lo--, hi--5  else: lo--, hi++6  if hi<0: return false7  lo=max(lo,0)8return lo==0

Input

array
[0]

Output

answer
—

Check yourself

3 quick questions about this walkthrough. A wrong answer costs nothing.

Examples

Example 1

Input:
s = "(*)"
Output:
true
Explanation:
The * acts as ( or ) or empty → valid.

Example 2

Input:
s = "(*))"
Output:
true
Explanation:
One * balances the extra bracket.

Example 3

Input:
s = ")("
Output:
false
Explanation:
No * to fix the order → invalid.

Practice this problem:LeetCode(opens in a new tab)Search GeeksforGeeks(opens in a new tab)

Finished the walkthrough? Add it to your streak.