# O(n) Java solution

• A string is a valiate string iff

1. From begin to any position, count of '(' + count of '*' >= count of ')'
2. From end back to any position, count of ')' + count of '*' >= count of '('

Proof:
If 1, any ')' will always be matched by a '(' or '' on its left
If 2, any '(' will always be matched by a ')' or '
' on its right
So if 1 and 2 are satisfied, the string is valid
Obviously if 1 or 2 are not satisfied, the string is invalid.

``````    int toId(char c) {
return "()*".indexOf(c);
}
public boolean checkValidString(String s) {
int sz = s.length();
int[] fromLeft = new int[3], fromRight = new int[3];
for (int i = 0; i < sz; ++i) {
char c = s.charAt(i);
int id = toId(c);
fromLeft[id]++;
if (fromLeft[0]+fromLeft[2]<fromLeft[1])return false;
}
for (int i = sz-1;i>=0;--i){
char c=s.charAt(i);
int id=toId(c);
fromRight[id]++;
if (fromRight[1]+fromRight[2]<fromRight[0])return false;
}
return true;
}
``````

• very smart solution!

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