Katkat
Back

Decide Whether a Parenthesis String With Star Wildcards Can Be Balanced

OracleSoftware Engineer · Technical Screen
MediumSoftware EngineerTechnical ScreenCoding & Algorithms

Last updated

Decide whether a string of parentheses and stars can become a balanced parenthesis string when each star may independently act as an opening parenthesis, a closing parenthesis or an empty string. Tests reasoning over many possible replacements at once and edge cases with unmatched parentheses near either end.

Given a string made only of the characters (, ) and *, decide whether it can be turned into a balanced parenthesis string by replacing every *, independently of the others, with (, with ), or with the empty string.

A parenthesis string is balanced when, reading from left to right, the number of ) seen so far never exceeds the number of ( seen so far, and the two counts are equal at the end. The empty string is balanced.

Function Signature

def can_be_balanced(s: str) -> bool:

Rules

  • Each * is replaced on its own; two stars may be replaced differently.
  • The ( and ) characters stay exactly where they are; only stars change.
  • Return True if at least one way of replacing the stars yields a balanced string, and False otherwise.

Constraints

  • 1 <= len(s) <= 100
  • Every character of s is (, ) or *.

Examples

Example 1

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

Replacing the star with ( gives (()), which is balanced.

Example 2

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

The ) at index 0 has nothing before it that could open a pair, so every replacement fails at the first character.

Example 3

Input: s = "*(*"
Output: True

Replacing the first star with the empty string and the second with ) gives ().