Valid Parenthesis String

LeetCode 678: Valid Parenthesis String Solution & Explanation

Problem Overview

TL;DR: Maintain the smallest and largest possible number of unmatched opening parentheses while scanning the string, rejecting impossible prefixes and accepting only when the minimum possible count reaches zero.

In LeetCode 678: Valid Parenthesis String, each character is either (, ), or *. A wildcard can represent an opening parenthesis, a closing parenthesis, or an empty character. The goal is to determine whether at least one interpretation produces a correctly balanced parenthesis sequence.

This LeetCode 678 Solution uses a greedy range of possible unmatched-opening counts. It runs in linear time and is the optimal solution for interviews involving wildcard parenthesis validation.

Brute Force Approach for Valid Parenthesis String

The direct approach is to try every possible interpretation of every *:

• Replace * with (.
• Replace * with ).
• Replace * with an empty character.
• Check whether each resulting string is balanced.

A recursive implementation can process one character at a time:

function isValid(s, index, balance):
    if balance < 0:
        return false

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

    if s[index] == '(':
        return isValid(s, index + 1, balance + 1)

    if s[index] == ')':
        return isValid(s, index + 1, balance - 1)

    return (
        isValid(s, index + 1, balance + 1) OR
        isValid(s, index + 1, balance - 1) OR
        isValid(s, index + 1, balance)
    )

If there are k wildcard characters, this approach may explore up to 3^k interpretations. Its time complexity is therefore O(3^k), which is exponential.

Because s.length can be as large as 10^5, enumerating wildcard interpretations quickly causes Time Limit Exceeded. The algorithm must summarize all relevant wildcard choices instead of exploring them independently.

Algorithm Strategy: Stack Patterns

1. Initialize low and high to zero.
2. Scan the string from left to right.
3. For an opening parenthesis:
   • Increment low.
   • Increment high.
4. For a closing parenthesis:
   • Decrease low, but keep it at least zero.
   • Decrement high.
5. For a wildcard:
   • Decrease low, but keep it at least zero, representing the choice ).
   • Increment high, representing the choice (.
   • The unchanged possibility, representing an empty character, remains inside this interval.
6. If high becomes negative, return false immediately.
7. After processing the complete string, return whether low equals zero.

Execution Flow

1. The algorithm starts with the only possible stack size equal to zero: [low, high] = [0, 0].
2. Each ( must remain an opening parenthesis, so every possible stack size increases by one.
3. Each ) must match a previous opening parenthesis:
   • The maximum possible stack size decreases by one.
   • The minimum is clamped to zero because negative unmatched openings are not valid states.
4. Each * permits multiple transitions:
   • It can reduce the stack size by one.
   • It can increase the stack size by one.
   • It can leave the stack size unchanged. The interval [low, high] captures all these possibilities.
5. If high < 0, even the largest possible stack size is negative. Therefore, the current prefix already contains more required closing parentheses than any interpretation can match.
6. After the final character:
   • low == 0 means zero is among the possible final stack sizes, so a valid interpretation exists.
   • low > 0 means every interpretation leaves unmatched opening parentheses.

Proof of Correctness

We prove that the algorithm returns true exactly when some interpretation of the string is a valid parenthesis sequence.

Invariant

After processing any prefix of s:

• low is the smallest possible number of unmatched ( characters among all valid interpretations of that prefix.
• high is the largest possible number of unmatched ( characters among all valid interpretations of that prefix.
• If high < 0, no valid interpretation of the prefix exists.

Maintenance

• For (, every interpretation adds one unmatched opening parenthesis. Both bounds increase by one.
• For ), every interpretation removes one unmatched opening parenthesis. The upper bound decreases by one. The lower bound is clamped at zero because an interpretation cannot have a negative number of unmatched openings.
• For *, interpreting it as ) can decrease the count, interpreting it as ( can increase the count, and interpreting it as empty can preserve the count. The resulting possible counts are contained within the updated interval.

Thus, the invariant is maintained after every character.

Rejection

If high < 0, even the largest possible unmatched-opening count is negative. This means the prefix has more closing parentheses than any wildcard or opening parenthesis can match. No continuation can repair an invalid prefix, so returning false is correct.

Acceptance

At the end of the string, a valid parenthesis sequence must have zero unmatched opening parentheses. If low == 0, zero is reachable within the range of possible final counts, so at least one wildcard interpretation is balanced. If low > 0, every interpretation leaves an unmatched opening parenthesis, so the string is invalid.

Therefore, the algorithm is correct.

Pattern Reuse Notes

The following problems share the same pattern/subpattern:

• LeetCode 32: Longest Valid Parentheses
• LeetCode 20: Valid Parentheses
• LeetCode 921: Minimum Add to Make Parentheses Valid
• LeetCode 1963: Minimum Number of Swaps to Make the String Balanced

Each problem relies on the same underlying valid-parentheses matching constraint: prefixes must not contain more closing parentheses than available opening parentheses, and the final unmatched count determines validity or the required correction. The exact objective differs, but stack state, balance tracking, and prefix validation are applied similarly.

Reference Implementation

C++ Solution for LeetCode 678

1class Solution {
2public:
3    bool checkValidString(string s) {
4        int low = 0;
5        int high = 0;
6
7        for (char c : s) {
8            if (c == '(') {
9                ++low;
10                ++high;
11            } else if (c == ')') {
12                low = max(0, low - 1);
13                --high;
14            } else {
15                low = max(0, low - 1);
16                ++high;
17            }
18
19            if (high < 0) {
20                return false;
21            }
22        }
23
24        return low == 0;
25    }
26};

Java Solution for LeetCode 678

1class Solution {
2    public boolean checkValidString(String s) {
3        int low = 0;
4        int high = 0;
5
6        for (int i = 0; i < s.length(); i++) {
7            char c = s.charAt(i);
8
9            if (c == '(') {
10                low++;
11                high++;
12            } else if (c == ')') {
13                low = Math.max(0, low - 1);
14                high--;
15            } else {
16                low = Math.max(0, low - 1);
17                high++;
18            }
19
20            if (high < 0) {
21                return false;
22            }
23        }
24
25        return low == 0;
26    }
27}

Python Solution for LeetCode 678

1class Solution:
2    def checkValidString(self, s: str) -> bool:
3        low = 0
4        high = 0
5
6        for char in s:
7            if char == '(':
8                low += 1
9                high += 1
10            elif char == ')':
11                low = max(0, low - 1)
12                high -= 1
13            else:  # '*'
14                low = max(0, low - 1)
15                high += 1
16
17            if high < 0:
18                return False
19
20        return low == 0