LeetCode 678 solution using the Greedy pattern

LeetCode problem link: 678. Valid Parenthesis String

LeetCode 678. Valid Parenthesis String problem description

Medium level problem.

Given a string s containing only three types of characters: '(', ')' and '*', return true if s is valid.

The following rules define a valid string:

Any left parenthesis '(' must have a corresponding right parenthesis ')'.
Any right parenthesis ')' must have a corresponding left parenthesis '('.
Left parenthesis '(' must go before the corresponding right parenthesis ')'.
'*' could be treated as a single right parenthesis ')' or a single left parenthesis '(' or an empty string "".

Example 1:

Input: s = "()"
Output: true

Example 2:

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

Example 3:

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

Example 4:

Input: s = "("
Output: false

Constraints:

1 <= s.length <= 100
s[i] is '(', ')' or '*'.

LeetCode 678. Valid Parenthesis String problem solution

For solving this problem we can use the Greedy pattern and keep a range of possible numbers of unmatched opening parentheses:

low - the minimum possible number of unmatched '('.
high - the maximum possible number of unmatched '('.

For each character:

'(' increases both low and high.
')' decreases both low and high.
'*' can be '(', ')', or empty, so it decreases low and increases high.

low cannot be negative, because a negative number of unmatched opening parentheses is not meaningful, so set it to 0 when it drops below 0.

If high < 0, there are more closing parentheses than can possibly be matched, so return false immediately.

After processing the whole string, the string is valid only if low == 0. This means there is at least one interpretation of all '*' characters that leaves no unmatched opening parentheses.

Patterns | Techniques | Data Structures

Greedy pattern

Complexity

Time complexity: O(n) - we scan the string once and do constant work for each character.
Space complexity: O(1) - only two variables, low and high, are used regardless of the input size.

LeetCode 678. Valid Parenthesis String problem: example

Consider:

s = "(*))"

Start with:

low = 0
high = 0

1. Character `'('`

An opening parenthesis must increase the number of unmatched opening parentheses:

low = 1
high = 1

Possible unmatched '(' counts: [1, 1].

2. Character `'*'`

'*' can be:

')' → decrease the count,
empty → keep the count,
'(' → increase the count.

So:

low = 0
high = 2

Possible unmatched '(' counts are in the range [0, 2].

3. Character `')'`

A closing parenthesis decreases both limits:

low = -1 -> 0
high = 1

We clamp low to 0.

Possible unmatched '(' counts: [0, 1].

4. Character `')'`

Again decrease both limits:

low = -1 -> 0
high = 0

Final state:

low = 0
high = 0

Because low == 0, the string is valid.

One valid interpretation is:

(*))
 ↓
(())

Here '*' is treated as '('.

LeetCode 678 C++ solution

class Solution {
public:
    bool checkValidString(string s) {
        int low = 0;
        int high = 0;

        // Track the minimum and maximum possible unmatched '('
        for(char c : s) {
            if(c == '(') {
                low++;
                high++;
            } else if(c == ')') {
                low--;
                high--;
            } else {
                // '*' can be ')', empty, or '('
                low--;
                high++;
            }

            // The minimum number of unmatched '(' cannot be negative
            if(low < 0) low = 0;

            // Too many ')' to match in every possible interpretation
            if(high < 0) return false;
        }

        // At least one interpretation must close every '('
        return low == 0;
    }
};

LeetCode 678 Java solution

class Solution {
    public boolean checkValidString(String s) {
        int low = 0;
        int high = 0;

        // Track the minimum and maximum possible unmatched '('
        for(int i = 0; i < s.length(); i++) {
            char c = s.charAt(i);

            if(c == '(') {
                low++;
                high++;
            } else if(c == ')') {
                low--;
                high--;
            } else {
                // '*' can be ')', empty, or '('
                low--;
                high++;
            }

            // The minimum number of unmatched '(' cannot be negative
            if(low < 0) low = 0;

            // Too many ')' to match in every possible interpretation
            if(high < 0) return false;
        }

        // At least one interpretation must close every '('
        return low == 0;
    }
}

LeetCode 678 JavaScript solution

var checkValidString = function(s) {
    let low = 0;
    let high = 0;

    // Track the minimum and maximum possible unmatched '('
    for(const c of s) {
        if(c === '(') {
            low++;
            high++;
        } else if(c === ')') {
            low--;
            high--;
        } else {
            // '*' can be ')', empty, or '('
            low--;
            high++;
        }

        // The minimum number of unmatched '(' cannot be negative
        if(low < 0) low = 0;

        // Too many ')' to match in every possible interpretation
        if(high < 0) return false;
    }

    // At least one interpretation must close every '('
    return low === 0;
};

LeetCode 678 TypeScript solution

function checkValidString(s: string): boolean {
    let low = 0;
    let high = 0;

    // Track the minimum and maximum possible unmatched '('
    for(const c of s) {
        if(c === '(') {
            low++;
            high++;
        } else if(c === ')') {
            low--;
            high--;
        } else {
            // '*' can be ')', empty, or '('
            low--;
            high++;
        }

        // The minimum number of unmatched '(' cannot be negative
        if(low < 0) low = 0;

        // Too many ')' to match in every possible interpretation
        if(high < 0) return false;
    }

    // At least one interpretation must close every '('
    return low === 0;
}

LeetCode 678 Python solution

class Solution:
    def checkValidString(self, s: str) -> bool:
        low = 0
        high = 0

        # Track the minimum and maximum possible unmatched '('
        for c in s:
            if c == '(':
                low += 1
                high += 1
            elif c == ')':
                low -= 1
                high -= 1
            else:
                # '*' can be ')', empty, or '('
                low -= 1
                high += 1

            # The minimum number of unmatched '(' cannot be negative
            if low < 0:
                low = 0

            # Too many ')' to match in every possible interpretation
            if high < 0:
                return False

        # At least one interpretation must close every '('
        return low == 0