921. Minimum Add to Make Parentheses Valid | LeetCode Solution
A parentheses string is valid if and only if:
- It is the empty string,
- It can be written as
AB
(A
concatenated withB
), whereA
andB
are valid strings, or - It can be written as
(A)
, whereA
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.
- For example, if
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 <= 1000
s[i]
is either'('
or')'
.
class Solution {
public:
int minAddToMakeValid(string s) {
int left=0,right=0;
for(char c:s){
if(c=='(')right++;
else if(right>0)right--;
else left++;
}
return left+right;
}
};
0 Comments
If you have any doubts/suggestion/any query or want to improve this article, you can comment down below and let me know. Will reply to you soon.