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.

Core Basics

• Opening move: classify the object (interval, multiset, trie node, bitmask, overlapping sub-intervals…) and whether the answer lives in an enumeration, ordering, partition, graph walk, DP table, etc.
• Contracts: spell what a valid partial solution looks like at each step—the thing you inductively preserve.
• Complexity anchors: state the brute upper bound and the structural fact (sorting, monotonicity, optimal substructure, greedy exchange, hashability) that should beat it.

Understanding

• Why brute hurts: name the repeated work or state explosion in one sentence.
• Why optimal is safe: the invariant / exchange argument / optimal-subproblem story you would tell a staff engineer.

Memory Hooks

• One chant / rule: a single memorable handle (acronym, operator trick, or shape) you can recall under time pressure.

Recognition Cues

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

Study Pattern (SDE3+)

• 0–3 min: restate I/O and brittle edges aloud, then verbalize two approaches with time/space before you touch the keyboard.
• Implementation pass: one-line invariant above the tight loop; state what progress you make each iteration.
• 5 min extension: pick one constraint twist (immutable input, stream, bounded memory, parallel readers) and explain what in your solution breaks without a refactor.

Diagram

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

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;
}

Walkthrough

Scan maintaining [lowBalance, highBalance] of achievable opening balances:

• ( raises both.
• ) lowers both (low floored at 0).
• * either opens extra (high++), closes (low-- if possible), or empty (both adjust).

If highBalance drops below zero, too many ) for any assignment.

Edge Cases

• * only → true (empty or balanced via pairs)
• Empty string → true per definition

Pitfalls

• Forgetting to clamp lowBalance at 0
• Mixing up stack greedy vs range greedy

Similar Problems

• 20. Valid Parentheses — no wildcards; stack baseline.
• 763. Partition Labels — greedy scanning discipline.
• 055. Jump Game — feasibility interval intuition.

Variants

• Count valid assignments → DP.

Mind-Map Tags

#greedy #parentheses #wildcard #balance-range #medium