Valid Parenthesis String

Medium

The problem

The string s has only the characters "(", ")" and "*". Each "*" can act as "(", as ")", or as an empty character. Return true if you can choose so that the brackets are correctly matched: every "(" has a later ")" and every ")" has an earlier "(".

Example 1
Input: s = "(*)"
Output: true
The "*" can be empty, giving "()".
Example 2
Input: s = "(*))"
Output: true
Make the "*" a "(" to get "(())".
Example 3
Input: s = "(((*"
Output: false
Even if the "*" closes one bracket, two "(" stay open.

Limits

1 ≤ len(s) ≤ 100,000
s has only the characters "(", ")" and "*"

Write it in Go. Try for about 20 minutes on paper first, then open one hint at a time.

Try it here

Write Go. Common packages like fmt and sort are imported for you. Keep the function name and inputs the same.

Hints, one at a time

Nudge

"*" can be three things. Instead of choosing, track the range of possible open counts.

The idea

Keep lo and hi = min/max possible number of unmatched "(". "(" → both+1, ")" → both−1, "*" → lo−1, hi+1. Clamp lo ≥ 0; fail if hi < 0; valid if lo == 0 at the end.

Target: O(n) time, O(1) space

Go function shape

func checkValidString(s string) bool

Reference solution

Tested with go test. Try it yourself first, then compare.

// CheckValidString: '*' can be '(', ')' or empty. Instead of choosing, track the RANGE of possible counts of
// unmatched '(' : lo (stars all used as ')') up to hi (stars all used as '(').
func CheckValidString(s string) bool {
	lo, hi := 0, 0
	for _, c := range s {
		switch c {
		case '(':
			lo++
			hi++
		case ')':
			lo--
			hi--
		default:
			lo--
			hi++
		}
		if hi < 0 {
			return false // even with every star as '(' there are too many ')'
		}
		lo = max(lo, 0) // a negative count just means some stars were treated as empty
	}
	return lo == 0
}

Read the lesson: Greedy