Valid Parenthesis String

Medium Problem 140 of 151 Java and Python

Problem

Given a string s containing only (, ) and *, return true if it can be valid.

Each * may be treated as (, as ) or as an empty string. Valid means every bracket is matched in the correct order.

Example 1

Input: s = "()"
Output: true

Example 2

Input: s = "(*)"
Output: true

Example 3

Input: s = "(*))"
Output: true
Why: Treat * as (.

Example 4

Input: s = ")*("
Output: false

Constraints

1 ≤ s.length ≤ 100

Explanation

Without stars, you track one number: open brackets so far. With stars, that number becomes a range [low, high]: ( raises both, ) lowers both, * lowers low and raises high.

If high drops below 0, there are too many ) even with every star as (. Never let low go below 0 (a star would just be empty instead). The string is valid if low can end at 0.

Approach 1 · Naive

Try all three meanings of each star

Time O(3ⁿ)
Space O(n)

Recursively try * as (, ) and empty, tracking the open count.

check(i, open): fail if open < 0; at the end, succeed if open == 0.
( → open + 1; ) → open - 1; * → try all three.

Java

class Solution {
    public boolean checkValidString(String s) {
        return check(s, 0, 0);
    }

    private boolean check(String s, int i, int open) {
        if (open < 0) {
            return false;
        }
        if (i == s.length()) {
            return open == 0;
        }
        char c = s.charAt(i);
        if (c == '(') {
            return check(s, i + 1, open + 1);
        }
        if (c == ')') {
            return check(s, i + 1, open - 1);
        }
        return check(s, i + 1, open + 1) || check(s, i + 1, open - 1) || check(s, i + 1, open);
    }
}

Python

class Solution:
    def checkValidString(self, s: str) -> bool:
        def check(i, open_count):
            if open_count < 0:
                return False
            if i == len(s):
                return open_count == 0
            c = s[i]
            if c == "(":
                return check(i + 1, open_count + 1)
            if c == ")":
                return check(i + 1, open_count - 1)
            return check(i + 1, open_count + 1) or check(i + 1, open_count - 1) or check(i + 1, open_count)

        return check(0, 0)

Approach 2 · Optimal

Greedy range of open counts

Time O(n)
Space O(1)

Track the smallest and largest possible number of unmatched (.

low = high = 0.
(: both +1. ): both -1. *: low - 1, high + 1.
If high < 0, return false; clamp low to at least 0.
Return low == 0.

Java

class Solution {
    public boolean checkValidString(String s) {
        int low = 0;
        int high = 0;
        for (char c : s.toCharArray()) {
            if (c == '(') {
                low++;
                high++;
            } else if (c == ')') {
                low--;
                high--;
            } else {
                low--;
                high++;
            }
            if (high < 0) {
                return false;
            }
            low = Math.max(low, 0);
        }
        return low == 0;
    }
}

Python

class Solution:
    def checkValidString(self, s: str) -> bool:
        low = high = 0
        for c in s:
            if c == "(":
                low, high = low + 1, high + 1
            elif c == ")":
                low, high = low - 1, high - 1
            else:
                low, high = low - 1, high + 1
            if high < 0:
                return False
            low = max(low, 0)
        return low == 0

Complexity compared

Approach	Time	Space
Naive Try all three meanings of each star	O(3ⁿ)	O(n)
Optimal Greedy range of open counts	O(n)	O(1)

Key takeaways

When a choice creates many possible states that are all numbers, tracking just the min and max can replace the search.

Your notes

Saved in this browser as you type.

Solved it on your own?

Mark it done to track your progress, or star it to come back before an interview.

Next problem