DSA interview question

Valid Parenthesis String (with Wildcards)

Hard · Data structures · Topics: greedy, string, stack

The problem

A template engine lets authors write * as a wildcard that can stand for (, ) or nothing at all. Before rendering, it must check whether the string can be read as balanced parentheses under some choice for each *. Trying all 3^k choices is exponential. Instead, track the range of possible open-bracket counts after each character: lo if every wildcard is used as ) when possible, and hi if every wildcard is used as (. If hi ever drops below 0, too many ) appeared. At the end, the string is valid if 0 is still reachable.

Example: "(*))" → true (the * becomes ().

Function signature

bool checkValidString(const string& s);  // characters '(', ')', '*'

Test cases

Input	Output	Explanation
`"()"`	`true`
`"(*)"`	`true`	* is empty
`"(*))"`	`true`	* is (
`")("`	`false`	Closes before anything opens
`"(((**"`	`false`	Two wildcards can close only two of three
`"**(("`	`false`	Trailing opens can't be closed

(Confirm: each * may independently be '(', ')' or empty; the empty string is valid.)

How interviewers phrase it

"Given a string containing '(', ')' and '', where '' can be treated as '(', ')' or an empty string, return true if the string is valid" (LeetCode 678).

Clarifying questions to ask

Can * be empty? (Yes.)
Is the empty string valid? (Yes.)
How long can s be? (Up to 100, but aim for O(n).)

Follow-ups to expect

"What do lo and hi mean?"
"Why clamp lo at 0?"
"Why fail when hi < 0?"
"Alternative approaches?"
"Complexity?"

Practise questions like this with a real engineer

On Practick another engineer interviews you live for 60 minutes on a question from this bank. They have the full interviewer guide beside the call: the expected answer to every follow-up, hints to give if you stall, and a scoring rubric. You get the model solution once the session settles. It is free: interview someone for an hour and you have earned your own.

Book a free mock interview