Pattern Recognition Drill
Medium Greedy
The Problem
Given a string with '(', ')', and '*' (* can be '(', ')' or empty), determine if it's valid.
What approach would you use?
Think about it before scrolling down.
Track lo (min open) and hi (max open). '(' → both++. ')' → both--. '*' → lo--, hi++. Valid if lo <= 0 <= hi throughout. O(n).
dp[i][open_count] = feasibility. O(n²) — overkill when greedy works.
Common Trap
Don't generate all 3^n possibilities for *. The lo/hi range tracking is the elegant O(n) solution.