Valid Parenthesis String

Medium· Range Tracking

Problem

A string contains "(", ")" and "*", where each "*" may act as "(", ")" or nothing. Return true if some choice for the stars makes the string a balanced parentheses string.

Examples

Input: s = "(*))"

Output: true

Treat the star as "(" to get "(())".

Input: s = "((*"

Output: false

At most one of the two open brackets can be closed.

Constraints

• 1 <= s.length <= 100
• s[i] is "(", ")" or "*"

Hints & approach

Hint 1

You do not know what each star is, but you can bound the number of open brackets.

Hint 2

Track the minimum and maximum possible open count as you scan.

Hint 3

If the maximum ever goes negative, fail; never let the minimum drop below zero.

Approachtry the hints first

Scan once, keeping lo and hi as the smallest and largest possible counts of unmatched "(". For "(" increment both; for ")" decrement both; for "*" decrement lo and increment hi. If hi drops below 0 there are too many ")" and you return false. Clamp lo at 0 since a negative open count is never a valid choice. At the end, the string is valid exactly when lo is 0.

Time O(n) · Space O(1)

← PreviousPartition Labels Next →Candy