Decide Whether a Parenthesis String With Star Wildcards Can Be Balanced
Company: Oracle
Role: Software Engineer
Category: Coding & Algorithms
Difficulty: medium
Interview Round: Technical Screen
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
```python
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**
```text
Input: s = "(*))"
Output: True
```
Replacing the star with `(` gives `(())`, which is balanced.
**Example 2**
```text
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**
```text
Input: s = "*(*"
Output: True
```
Replacing the first star with the empty string and the second with `)` gives `()`.
Overview: 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.