Valid Parenthesis String

Medium
221.

Valid Parenthesis String

Valid Parenthesis String is a medium coding problem on strings, dynamic programming and greedy, asked in Amazon, Google, Meta and Bloomberg interviews.

Given a string s containing only '(', ')' and '*', return true if s is valid.

The rules are the usual bracket-matching rules, and a '*' may stand for '(', for ')', or for the empty string.

Example 1

Input
s = "()"
Output
true

Example 2

Input
s = "(*)"
Output
true
Explanation
The star can be the empty string.

Example 3

Input
s = "(*))"
Output
true
Explanation
The star can be an opening bracket.

Constraints

  • 1 <= s.length <= 40
  • s consists of '(', ')' and '*'.
Write your solution here. Running it against the tests needs a free account — what you type comes with you.Sign in to run
/**
 * @param {string} s
 * @return {boolean}
 */
var checkValidString = function(s) {
    // Write your code here
    
};

Sign in to run your own test cases

Sign in

Valid Parenthesis String — Solution in Python, Java & C++

Valid Parenthesis String solution explained: step-by-step approach, complexity and code in Python, Java, C++ and JavaScript. A medium problem.

Valid Parenthesis String is a medium coding problem on strings, dynamic programming and greedy, asked in Amazon, Google, Meta and Bloomberg interviews.

Problem statement

Given a string s containing only '(', ')' and '*', return true if s is valid.

The rules are the usual bracket-matching rules, and a '*' may stand for '(', for ')', or for the empty string.

Example 1

Input: s = "()"
Output: true

Example 2

Input: s = "(*)"
Output: true
Explanation: The star can be the empty string.

Example 3

Input: s = "(*))"
Output: true
Explanation: The star can be an opening bracket.

Constraints

  • 1 <= s.length <= 40
  • s consists of '(', ')' and '*'.

Hints for Valid Parenthesis String

  1. Hint 1

    Instead of trying every meaning of every star, track the range of possible open-bracket counts.

  2. Hint 2

    lo assumes every star is a closing bracket (or empty); hi assumes every star is an opening bracket.

  3. Hint 3

    If hi ever drops below zero there are too many closers to fix; clamp lo at zero, and at the end the string is valid iff lo reached 0.

How to solve Valid Parenthesis String

Track the range of possible open-bracket counts: lo treats every star as a closer, hi treats every star as an opener. The string is valid if hi never goes negative and lo can end at 0.

Approach

  1. Set lo = hi = 0.
  2. For (: increment both. For ): decrement both. For *: lo -= 1, hi += 1.
  3. If hi < 0, return false; clamp lo to 0.
  4. Return lo == 0.

Why it works

Every achievable open-count after a prefix lies in [lo, hi], and every integer in that range is achievable because stars can be re-assigned one at a time. hi < 0 means even all-openers cannot absorb the closers; clamping lo discards impossible negative counts. Ending with 0 in range means some assignment balances.

Complexity

  • Time — O(n)
  • Space — O(1)

Pitfalls

  • Forgetting to clamp lo lets a later ( "cancel" an impossible negative balance.
  • Trying every star assignment is exponential; two stacks (one for (, one for *) is the other linear approach.

Reference solution

Python

def checkValidString(s: str) -> bool:
    lo = hi = 0
    for ch in s:
        if ch == "(":
            lo += 1
            hi += 1
        elif ch == ")":
            lo -= 1
            hi -= 1
        else:
            lo -= 1
            hi += 1
        if hi < 0:
            return False
        if lo < 0:
            lo = 0
    return lo == 0

Java

public static boolean checkValidString(String s) {
    int lo = 0, hi = 0;
    for (int i = 0; i < s.length(); i++) {
        char c = s.charAt(i);
        if (c == '(') { lo++; hi++; }
        else if (c == ')') { lo--; hi--; }
        else { lo--; hi++; }
        if (hi < 0) return false;
        if (lo < 0) lo = 0;
    }
    return lo == 0;
}

C++

bool checkValidString(string 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) return false;
        if (lo < 0) lo = 0;
    }
    return lo == 0;
}

JavaScript

var checkValidString = function(s) {
    let lo = 0, hi = 0;
    for (let i = 0; i < s.length; i++) {
        const c = s[i];
        if (c === "(") { lo++; hi++; }
        else if (c === ")") { lo--; hi--; }
        else { lo--; hi++; }
        if (hi < 0) return false;
        if (lo < 0) lo = 0;
    }
    return lo === 0;
};

Also on the editorial tab: C, C#, Go, Kotlin, PHP, Ruby, Rust, Swift, TypeScript.

All 515 strings problems · the whole catalogue

Learn the technique: Strings · Dynamic Programming