Practice › Greedy
Valid Parenthesis String
Medium · Greedy · Asked at Amazon, Google, Microsoft, Meta
The string contains (, ) and *. Each * can be treated as (, ) or an empty string. Print YES if some choice makes the string a valid parentheses string, otherwise NO.
Input
A single string s.
Output
YES or NO.
Constraints
- 1 ≤ |s| ≤ 10^5
Track the range [lo, hi] of possible open-bracket counts: "(" adds 1 to both, ")" subtracts 1, "*" gives lo − 1 and hi + 1. Clamp lo at 0; if hi < 0 it fails; at the end lo must be 0.
Example 1
Input
(*)
Output
YES
Example 2
Input
(*))
Output
YES
Hints
- Instead of trying all choices for each *, track the range of possible open-bracket counts [lo, hi].
- "(" → lo+1, hi+1; ")" → lo−1, hi−1; "*" → lo−1, hi+1. If hi < 0 it is invalid; keep lo ≥ 0. At the end, valid iff lo == 0.
Approach
hi is the most open brackets possible (every * as "("), lo the fewest (every * as ")", but never below 0 because a negative count is not a valid prefix). If hi ever drops below 0, even the most generous interpretation has too many ")". At the end, a count of 0 must be achievable, which is exactly lo == 0. Every value between lo and hi is achievable, which is why tracking only the two ends is enough.
Complexity: O(n) time · O(1) space
Solution
C++ solution
#include <bits/stdc++.h>
using namespace std;
int main() {
string s;
cin >> s;
int lo = 0, hi = 0;
for (char c : s) {
if (c == '(') lo++, hi++;
else if (c == ')') lo--, hi--;
else lo--, hi++;
if (hi < 0) {
cout << "NO\n";
return 0;
}
lo = max(lo, 0);
}
cout << (lo == 0 ? "YES" : "NO") << "\n";
return 0;
}Python solution
s = input().strip()
lo = hi = 0
ok = True
for c in s:
if c == "(":
lo, hi = lo + 1, hi + 1
elif c == ")":
lo, hi = lo - 1, hi - 1
else:
lo, hi = lo - 1, hi + 1
if hi < 0:
ok = False
break
lo = max(lo, 0)
print("YES" if ok and lo == 0 else "NO")Java solution
import java.util.*;
public class Main {
public static void main(String[] args) {
String s = new Scanner(System.in).next();
int lo = 0, hi = 0;
for (char c : s.toCharArray()) {
if (c == '(') { lo++; hi++; }
else if (c == ')') { lo--; hi--; }
else { lo--; hi++; }
if (hi < 0) {
System.out.println("NO");
return;
}
lo = Math.max(lo, 0);
}
System.out.println(lo == 0 ? "YES" : "NO");
}
}Solve Valid Parenthesis String online · All practice problems