Getting everything ready for you…

Loading courses, problems and your progress. This takes just a moment.

0s

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

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

  1. Instead of trying all choices for each *, track the range of possible open-bracket counts [lo, hi].
  2. "(" → 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