678. Valid Parenthesis String

NeetCode: Valid Parenthesis String · LeetCode: 678. Valid Parenthesis String · Difficulty: Medium

A string contains only (, ) and *. A * may be treated as (, ) or an empty string. Return true if the string can be made a valid parentheses string.

Example

Input:  s = "(*))"    Output: true    (treat * as "(")
Input:  s = "((*"     Output: false

Brute force: try all three meanings of every star

Recurse through the string with the current count of open brackets. A * branches three ways. The count must never go negative and must be zero at the end. Without memoization this is exponential in the number of stars.

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);
    }
}

public class Main {
    public static void main(String[] args) {
        Solution s = new Solution();
        System.out.println(s.checkValidString("(*))"));
        System.out.println(s.checkValidString("((*"));
        System.out.println(s.checkValidString(""));
    }
}

true
false
true

Time: O(3^n) in the worst case. Space: O(n) recursion depth. Each call adds a stack frame, so a long string of stars can overflow the thread stack in Java.

Optimal: track the range of possible open counts

Instead of choosing a meaning for each star, track the range [lo, hi] of open-bracket counts that are still possible after each character:

• ( raises both lo and hi by one.
• ) lowers both by one.
• * could be ), empty or (, so lo drops by one and hi rises by one.

hi is the case where every star is (; lo is the case where every star closes as much as possible. If hi goes below zero, even the most open-friendly reading has too many closers, so the answer is false. lo is clamped at zero, since a negative count means some star was not used as ). At the end the string is valid exactly when lo == 0, meaning zero open brackets is achievable. Every count between lo and hi is reachable because stars can also be empty, so the two ends are enough.

Trace for (*)):

char  lo hi
(     1  1
*     0  2     (lo = 1-1, hi = 1+1)
)     0  1     (lo would be -1, clamped to 0)
)     0  0     -> lo == 0, valid

class Solution {
    public 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;
            }
            lo = Math.max(lo, 0);
        }
        return lo == 0;
    }
}

public class Main {
    public static void main(String[] args) {
        Solution s = new Solution();
        System.out.println(s.checkValidString("(*))"));
        System.out.println(s.checkValidString("((*"));
        System.out.println(s.checkValidString(""));
        System.out.println(s.checkValidString("*)("));
    }
}

true
false
true
false

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

How to explain it in an interview

• Start with recursion on the current open count, trying all three meanings of each star: O(3^n), or O(n^2) with memoization on (i, open).
• Observe that only the lowest and highest possible open count matter, not the individual star choices.
• Code it in steps: lo = hi = 0; ( adds one to both; ) subtracts one from both; * does lo -= 1, hi += 1; return false if hi < 0; clamp lo at 0; return lo == 0.
• State the complexity: O(n) time, O(1) space.
• Pitfalls: lo is clamped because a negative open count is impossible, and only hi < 0 is a failure because a negative lo can be repaired by choosing other meanings. The final check matters: for *)( the range never fails, but the last ( leaves lo == 1, so the answer is false.