Brackets With Wildcards

MediumGreedy

Problem

A template string s contains (, ) and the wildcard *. Each wildcard may later be replaced by (, by ) or by nothing.

Return true if some choice of replacements makes the string a balanced bracket sequence (every ( closed by a later ), never closing more than is open). The empty string is balanced.

Example 1

Input:
s = "(*))"
Output:
true

Turn the wildcard into (: "(())".

Example 2

Input:
s = ")*("
Output:
false

The first character closes a bracket that was never opened, whatever the wildcard becomes.

Example 3

Input:
s = "(*()"
Output:
true

Turn the wildcard into ): "()()".

Constraints

  • 1 ≤ s.length ≤ 10^5
  • s[i] is '(', ')' or '*'

Hint

Show the first hint

Without wildcards you would track a single counter of open brackets. What does a wildcard do to that counter?

Walkthrough

How to approach it

01Clarify before coding

  • Can a wildcard become an empty string? Yes, three options per wildcard.
  • Is only one bracket type involved? Yes, just round brackets.
  • Is the answer just a boolean? Yes.

02Brute force

Try all 3^w replacements of the w wildcards and check each result with a counter.

Cost: O(3^w · n): exponential. A DP over (index, open count) is O(n²), still 10^10 here.

The rest of the walkthrough is in the app

The full walkthrough (key insight, step-by-step, dry run, complexity, edge cases, pitfalls, follow-ups) and solutions in Python and JavaScript are in the app, next to an editor and a terminal that runs your code against the tests.

Solve it in the browserStart free

This problem is part of Pro.