LeetCode 678 · Medium · Greedy

Valid Parenthesis String

The string s holds (, ) and *, where each * may act as (, as ), or as nothing. Return true if some choice makes the parentheses balanced.

O(n)time
O(1)space
[min, max]open-count range

only ( ) * · 1–14 characters

open-count range after each character

public boolean checkValidString(String s) { int leftMin = 0; // range of open counts int leftMax = 0; for (char c : s.toCharArray()) { if (c == '(') { leftMin++; leftMax++; } else if (c == ')') { leftMin--; leftMax--; } else { leftMin--; leftMax++; } if (leftMax < 0) { return false; } if (leftMin < 0) { leftMin = 0; // can't have negative opens } } return leftMin == 0;}
c
—
leftMin
0
leftMax
0

Why it works

  1. Brute force tries all three roles for every *: O(3ᵏ) for k stars. A DP over (index, open count) brings it to O(n²).
  2. Track a range, not a choice. After each character, the number of unmatched ( could be any value in [leftMin, leftMax], depending on how the stars were used. ( shifts the range up, ) shifts it down, * widens it both ways.
  3. Two numbers per character: O(n) time, O(1) space. If even leftMax drops below 0, too many ) arrived: fail at once. At the end, balanced is possible exactly when 0 is in the range, that is leftMin == 0.
  4. Pitfall: clamp leftMin at 0. A negative open count is impossible; it just means the choices that made it are ruled out. Without the clamp, "(*)" ends at leftMin = -1 and wrongly fails.
  5. Order matters: "*)(" has balanced counts but fails, because the last ( leaves leftMin = 1. Related: Valid Parentheses (20) is the version without stars, a plain counter or stack.