C++ Greedy, O(N) Time O(1) Space

• 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;
}
};
``````

Looks like your connection to LeetCode Discuss was lost, please wait while we try to reconnect.