Valid Parenthesis String - Video Solutions

Problem Overview: You receive a string containing three characters: (, ), and *. The asterisk acts as a wildcard and can represent (, ), or an empty string. The task is to determine whether the string can be interpreted as a valid parentheses sequence.

This problem looks like a typical parentheses validation task but becomes tricky because * can play multiple roles. You need a strategy that keeps track of possible interpretations without trying every combination. Efficient solutions rely on techniques from stack processing and greedy algorithms, both commonly used when validating structured strings.

Approach 1: Stack-based Tracking (O(n) time, O(n) space)

This approach uses two stacks: one for indices of ( characters and another for indices of *. While iterating through the string, push positions of opening brackets and asterisks onto their respective stacks. When encountering ), try to match it with the most recent (. If none exists, use a * as a substitute opening bracket. After processing the entire string, there may still be unmatched (. Pair them with later * characters by comparing indices to ensure ordering is valid. This approach works because stacks naturally model the nested structure of parentheses while allowing deferred decisions for wildcard characters.

Approach 2: Greedy Balance Range (O(n) time, O(1) space)

The greedy solution tracks the range of possible open-parenthesis counts instead of exact matches. Maintain two counters: low (minimum possible open brackets) and high (maximum possible open brackets). When reading (, increment both. When reading ), decrement both. When reading *, treat it flexibly: decrement low (as if it were )) and increment high (as if it were (). Clamp low to zero because open counts cannot be negative. If high ever drops below zero, the string cannot be valid. By the end of the scan, a valid configuration exists if low == 0. This method works because it keeps track of the entire feasible range of interpretations without explicitly constructing them.

Recommended for interviews: The greedy balance method is the solution most interviewers expect. It runs in O(n) time with O(1) space and demonstrates strong reasoning about state ranges rather than brute-force enumeration. The stack-based approach is still valuable during interviews because it shows clear thinking about matching order and wildcard handling, but the greedy method highlights deeper optimization skills.