A parentheses string is valid if and only if:
AB (A concatenated with B), where A and B are valid strings, or(A), where A is a valid string.You are given a parentheses string s. In one move, you can insert a parenthesis at any position of the string.
s = "()))", you can insert an opening parenthesis to be "(()))" or a closing parenthesis to be "())))".Return the minimum number of moves required to make s valid.
Example 1:
Input: s = "())" Output: 1
Example 2:
Input: s = "((("
Output: 3
Constraints:
1 <= s.length <= 1000s[i] is either '(' or ')'.class Solution {
public int minAddToMakeValid(String s) {
int n = s.length(), lt = 0, rt = 0, ct = 0;
char[] cs = s.toCharArray();
for(; rt<n; rt++){
cs[lt] = cs[rt];
if(lt>0 && cs[rt]==')' && cs[lt-1]=='(')
lt--;
else lt++;
}
return lt;
}
}