678. Valid Parenthesis String

At a Glance

Topic: greedy
Pattern: Greedy (balance range) / stack variant
Difficulty: Medium
Companies: Google, Facebook, Amazon, Apple, Adobe
Frequency: Medium
LeetCode: 678

Problem (one-liner)

Given s with '(', ')', '*' where * can be '(', ')', or empty, determine whether some assignment makes s a valid parentheses string. Input: s. Output: boolean.

Recognition Cues

Wildcards * with three interpretations
Track possible range of balance after processing prefix (greedy low/high)
Or two-stack approach for ( and * indices

Diagram

At-a-glance flow (replace with problem-specific Mermaid as you refine this note). camelCase node IDs; no spaces in IDs.

Loading diagram…

Approaches

DP on index and balance — O(n²) time.
Greedy balance range — O(n) time / O(1) space. <- pick this in interview.

Optimal Solution

Go

package main

func checkValidString(s string) bool {
	lowBalance := 0
	highBalance := 0
	for index := range s {
		ch := s[index]
		if ch == '(' {
			lowBalance++
			highBalance++
		} else if ch == ')' {
			if lowBalance > 0 {
				lowBalance--
			}
			highBalance--
		} else {
			if lowBalance > 0 {
				lowBalance--
			}
			highBalance++
		}
		if highBalance < 0 {
			return false
		}
	}
	return lowBalance == 0
}

JavaScript

function checkValidString(s) {
	let lowBalance = 0;
	let highBalance = 0;
	for (let index = 0; index < s.length; index++) {
		const ch = s[index];
		if (ch === '(') {
			lowBalance++;
			highBalance++;
		} else if (ch === ')') {
			if (lowBalance > 0) lowBalance--;
			highBalance--;
		} else {
			if (lowBalance > 0) lowBalance--;
			highBalance++;
		}
		if (highBalance < 0) return false;
	}
	return lowBalance === 0;
}