Difficulty: Medium · LeetCode 678

Problem

Given string s containing '(', ')', and '*' (where '*' can be '(', ')', or empty), return True if it is valid.

Understanding the problem

Instead of branching on every '*', track the range of possible open-parenthesis balances: [low, high]. high < 0 means even the most optimistic interpretation is invalid. low == 0 at the end means there's at least one valid interpretation.

Intuition

Track a range [low, high] of possible open balances. '(' increments both. ')' decrements both. '*' shrinks low and grows high. If high < 0, definitely invalid. Clamp low at 0 (balance can't go below 0 in any valid string).

Approach

Initialize low = 0, high = 0.
For each char in s:
'(': low += 1; high += 1.
')': low -= 1; high -= 1.
'*': low -= 1; high += 1.
If high < 0: return False.
Clamp: low = max(low, 0).
Return low == 0.

Naive Solution — Brute Force

Backtracking: try all three interpretations of each '*' recursively.

Python

class Solution:
    def checkValidString(self, s):

        def dfs(index, balance):
            if balance < 0:
                return False

            if index == len(s):
                return balance == 0

            char = s[index]

            if char == "(":
                return dfs(index + 1, balance + 1)

            if char == ")":
                return dfs(index + 1, balance - 1)

            # Try '*' as '(', ')', or ''
            return (
                dfs(index + 1, balance + 1)
                or dfs(index + 1, balance - 1)
                or dfs(index + 1, balance)
            )

        return dfs(0, 0)

C++

class Solution {
public:
    bool checkValidString(string s) {
        return dfs(s, 0, 0);
    }

private:
    bool dfs(const string& s, int index, int balance) {
        if (balance < 0) {
            return false;
        }

        if (index == (int)s.size()) {
            return balance == 0;
        }

        char c = s[index];

        if (c == '(') {
            return dfs(s, index + 1, balance + 1);
        }

        if (c == ')') {
            return dfs(s, index + 1, balance - 1);
        }

        // Try '*' as '(', ')', or ''
        return dfs(s, index + 1, balance + 1)
            || dfs(s, index + 1, balance - 1)
            || dfs(s, index + 1, balance);
    }
};

Java

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

    private boolean dfs(String s, int index, int balance) {
        if (balance < 0) {
            return false;
        }

        if (index == s.length()) {
            return balance == 0;
        }

        char c = s.charAt(index);

        if (c == '(') {
            return dfs(s, index + 1, balance + 1);
        }

        if (c == ')') {
            return dfs(s, index + 1, balance - 1);
        }

        // Try '*' as '(', ')', or ''
        return dfs(s, index + 1, balance + 1)
            || dfs(s, index + 1, balance - 1)
            || dfs(s, index + 1, balance);
    }
}

JavaScript

var checkValidString = function(s) {
    const dfs = (index, balance) => {
        if (balance < 0) {
            return false;
        }

        if (index === s.length) {
            return balance === 0;
        }

        const char = s[index];

        if (char === "(") {
            return dfs(index + 1, balance + 1);
        }

        if (char === ")") {
            return dfs(index + 1, balance - 1);
        }

        // Try '*' as '(', ')', or ''
        return (
            dfs(index + 1, balance + 1) ||
            dfs(index + 1, balance - 1) ||
            dfs(index + 1, balance)
        );
    };

    return dfs(0, 0);
};

Time: O(3ⁿ) · Space: O(n) recursion

Optimized Code (Python 3)

Python

class Solution:
    def checkValidString(self, s):
        low = 0
        high = 0

        for char in s:
            if char == "(":
                low += 1
                high += 1

            elif char == ")":
                low -= 1
                high -= 1

            else:  # '*'
                low -= 1
                high += 1

            if high < 0:
                return False

            low = max(low, 0)

        return low == 0

C++

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

        for (char c : s) {
            if (c == '(') {
                low++;
                high++;
            } else if (c == ')') {
                low--;
                high--;
            } else {  // '*'
                low--;
                high++;
            }

            if (high < 0) {
                return false;
            }

            low = max(low, 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;
    }
}

JavaScript

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

    for (const char of s) {
        if (char === "(") {
            low++;
            high++;
        } else if (char === ")") {
            low--;
            high--;
        } else {  // '*'
            low--;
            high++;
        }

        if (high < 0) {
            return false;
        }

        low = Math.max(low, 0);
    }

    return low === 0;
};

Time: O(n) · Space: O(1)

Takeaway

Pattern — Balance Range [low, high] — track the window of possible states instead of every individual state