Generated by Codex with GPT 5.6 Sol XHigh

Quick facts

Problem gist

The input contains opening parentheses, closing parentheses, and asterisks. Each * may act as (, act as ), or disappear. The task is to decide whether some choice for every asterisk makes the whole string a valid parenthesis sequence.

A valid sequence must satisfy two conditions: no prefix may contain more closing parentheses than opening ones, and the complete sequence must finish with no unmatched opening parentheses. Trying all three meanings for every * would explore up to 3^k possibilities for k asterisks, even though most of those possibilities differ only in how many openings remain unmatched.

Deriving the greedy range

After reading a prefix, the exact number of unmatched opening parentheses depends on the choices made for earlier asterisks. Instead of committing to those choices, keep the smallest and largest unmatched-open counts that are still possible:

  • minimum_open assumes asterisks close openings or disappear whenever that helps;
  • maximum_open assumes asterisks become opening parentheses whenever that helps.

The updates follow directly from each character:

  • ( increases both bounds;
  • ) decreases both bounds;
  • * can decrease the lower bound and increase the upper bound.

The lower bound is clamped at zero because a valid interpretation cannot carry a negative number of unmatched openings. If the upper bound ever becomes negative, every interpretation of that prefix has too many closing parentheses, so the full string is impossible. After the final character, minimum_open == 0 means at least one interpretation closes every opening.

For example, consider (*)). The reachable bounds after each character are [1, 1], [0, 2], [0, 1], and finally [0, 0]. The range reaches zero at the end, so choosing the asterisk as ( produces the valid sequence (()).

Why the range is enough

The bounds are not merely optimistic estimates. All feasible unmatched-open counts between them remain represented as the scan proceeds. A normal parenthesis shifts every feasible count in the same direction, while * expands the choices by one in both directions and can also leave the count unchanged. Discarding negative counts only removes interpretations that have already violated the prefix rule.

Therefore, maximum_open < 0 proves that no valid prefix interpretation exists, and a final lower bound of zero proves that some complete interpretation exists. The scan does constant work per character, so it runs in O(n) time and uses O(1) auxiliary space.

Python solution

The helper contains the reusable validation logic, while the small Solution adapter preserves LeetCode’s required method name. Invalid characters are rejected explicitly rather than being silently treated as wildcards.

def is_valid_parenthesis_string(expression: str) -> bool:
    """Return whether wildcards can make expression's parentheses valid."""
    minimum_open = 0
    maximum_open = 0

    for character in expression:
        if character == "(":
            minimum_open += 1
            maximum_open += 1
        elif character == ")":
            minimum_open -= 1
            maximum_open -= 1
        elif character == "*":
            # The wildcard may close an opening, disappear, or open a group.
            minimum_open -= 1
            maximum_open += 1
        else:
            raise ValueError(f"Unsupported character: {character!r}")

        if maximum_open < 0:
            # Even the interpretation with the most openings cannot repair
            # this prefix, so no later character can make it valid.
            return False

        # Negative counts describe invalid prefixes and can be discarded.
        minimum_open = max(0, minimum_open)

    return minimum_open == 0


class Solution:
    """LeetCode-compatible entry point."""

    def checkValidString(self, s: str) -> bool:
        return is_valid_parenthesis_string(s)

Interview follow-ups

Can the algorithm return one concrete interpretation of the asterisks?

Yes, but the two numeric bounds deliberately forget which positions produced them. To reconstruct an answer, scan with two stacks of indices: one for unmatched ( characters and one for available asterisks. A ) consumes a real opening if possible, otherwise an earlier asterisk; if neither exists, the string is invalid. After the scan, match every remaining opening with an asterisk that occurs later. Those matched asterisks become ), asterisks used while scanning become (, and all others disappear.

Using a later asterisk for each leftover opening preserves nesting order, which is why the construction works. It takes O(n) time and O(n) space for indices and the resulting assignment, compared with O(1) auxiliary space when only a Boolean answer is needed.

How would the solution count all valid interpretations?

The greedy interval cannot count paths because many different wildcard choices collapse to the same unmatched-open count. Use dynamic programming where ways[open_count] stores the number of interpretations of the current prefix with that many unmatched openings. A normal parenthesis makes one transition, while * makes up to three; transitions to negative counts are discarded. The answer is ways[0] after the final character.

There are at most O(n) possible open counts at each of n positions, so the method takes O(n^2) time and O(n) space with rolling arrays or maps. Counts grow exponentially, so a practical implementation may need arbitrary-precision integers or arithmetic modulo a requested value.

Could two directional scans solve the Boolean version too?

Yes. Scan left to right while treating every * as (; if closing parentheses ever outnumber that generous supply of openings, the string is invalid. Then scan right to left while treating every * as ); if openings ever outnumber possible closings, it is invalid. Passing both scans proves that the prefix and suffix constraints can be satisfied.

This approach is also O(n) time and O(1) space. It is concise, but the one-pass interval method exposes the full invariant in a single state and naturally supports streaming input.

What changes if the characters arrive as a stream?

Nothing essential. Preserve minimum_open and maximum_open between chunks and apply the same update to each arriving character. The stream can be rejected immediately when maximum_open becomes negative; when the producer signals the end, accept exactly when minimum_open is zero.

Processing still takes O(1) time per character and O(1) state, without retaining prior chunks. The important tradeoff is that a nonzero lower bound is not a failure until the stream actually ends, because future closing parentheses may still reduce it.

How would multiple bracket types affect the solution?

With (), [], and {}, a single count no longer describes the state because closing brackets must match the most recent opening of the same type. Without wildcards, a stack restores that ordering information and solves the problem in O(n) time and O(n) space.

If a wildcard may become any bracket, the state must represent possible stack contents rather than only possible stack heights. A dynamic program or memoized search can track those states, but their number may grow exponentially in the worst case. The constant-space interval trick works here precisely because one bracket type makes unmatched openings interchangeable.

How can the validator report the longest prefix that is valid by itself?

Run the same range scan and remember the latest index at which minimum_open is zero. At such a boundary, at least one interpretation of the prefix closes every opening. If maximum_open becomes negative, stop: that prefix and every longer prefix already contain an irreparable excess closing parenthesis.

This adds only one index to the O(1) state and keeps O(n) time. It reports the longest prefix ending at a feasible boundary, which is different from finding the longest valid substring starting anywhere; the latter generally needs additional positional information or dynamic programming.

When is the classic stack approach preferable?

For the Boolean problem, stacks of opening and wildcard indices also work: match closing parentheses during the forward scan, then pair remaining openings with later wildcards. The indices make ordering explicit and can produce a concrete assignment or precise diagnostics about unmatched positions.

That method remains O(n) time but uses O(n) space. The greedy bounds are preferable when only validity matters, while the stack version earns its extra memory when the interviewer asks for reconstruction, error locations, or edits to the original string.

Takeaway

The key is to postpone every wildcard decision. Tracking the minimum and maximum possible number of unmatched openings summarizes all useful interpretations of each prefix. If even the maximum falls below zero, the prefix is hopeless; if the minimum reaches zero at the end, some interpretation succeeds. That turns an exponential-looking search into one linear pass with constant space.