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.
Given a string `s` 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.
Implement `can_be_balanced(s)`.
### 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 (`true` / `false` in JavaScript, Java and C++).
### 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.
### Constraints
- `1 <= len(s) <= 100`
- Every character of `s` is `(`, `)` or `*`.
The answer is a single boolean; no numeric value crossing the function boundary can exceed 2^31-1.
Constraints
- 1 <= len(s) <= 100
- Every character of s is '(', ')' or '*'.
Examples
Input: ('(',)
Expected Output: False
Explanation: A lone '(' has nothing after it that could close it.
Input: (')',)
Expected Output: False
Explanation: A lone ')' has nothing before it that could open a pair.
Hints
- The balanced condition has two parts: a condition on every prefix while reading left to right, and an equality of counts at the end. A replacement must satisfy both.
- An unmatched '(' can only be closed by a ')' or a '*' that comes after it; an unmatched ')' can only be opened by a '(' or a '*' that comes before it.
- A '*' may also vanish, so a star is never forced to create an extra bracket.