In my algorithm I keep track of 3 values while traversing input string: `psum`

is current sum of brackets (+1 for `(`

, -1 for `)`

), `stars`

is current count of `*`

, `ssum`

is current sum of `*`

converted to brackets. At every step we need to check that total balance `psum + ssum`

is non-negative, `ssum`

is kept minimal possible i.e. we greedily convert every `*`

to `)`

thus `ssum`

is minimal possible and always within range `[-stars, +stars]`

. If `ssum`

is too small and total balance becomes negative then we can increase `ssum`

while it is within allowed bounds. At the end total balance should be `0`

otherwise if it is positive it means we can't create balance through `*`

's because we greedily chosen `)`

for each `*`

it means we kept lowest possible total balance at each step.

```
class Solution {
public:
bool checkValidString(string const & s) {
int psum = 0, stars = 0, ssum = 0;
for (char c: s) {
psum += c == '(' ? +1 : c == ')' ? -1 : 0;
ssum -= c == '*';
stars += c == '*';
if (psum + ssum < 0) {
if (ssum >= stars) return false;
++ssum;
}
}
if (psum + ssum > 0) return false;
return true;
}
};
```