Minimum Add to Make Parentheses Valid
Given a string S
of '('
and ')'
parentheses, we add the minimum number of parentheses ( '('
or ')'
, and in any positions ) so that the resulting parentheses string is valid.
Formally, a parentheses string is valid if and only if:
It is the empty string, or
It can be written as
AB
(A
concatenated withB
), whereA
andB
are valid strings, orIt can be written as
(A)
, whereA
is a valid string.
Given a parentheses string, return the minimum number of parentheses we must add to make the resulting string valid.
Example 1:
Input: "())"
Output: 1
Example 2:
Input: "((("
Output: 3
Example 3:
Input: "()"
Output: 0
Example 4:
Input: "()))(("
Output: 4
Note:
S.length <= 1000
S
only consists of'('
and')'
characters.
class Solution {
public int minAddToMakeValid(String S) {
int not_opened = 0, not_closed = 0;
for (int i = 0; i < S.length(); ++i) {
if (S.charAt(i) == '(') {
not_closed++;
} else if (not_closed > 0) {
not_closed--;
} else {
not_opened++;
}
}
return not_opened + not_closed;
}
}
Last updated