Algorithm
Problem Name: 921. Minimum Add to Make Parentheses Valid
A parentheses string is valid if and only if:
- It is the empty string,
- It can be written as
AB(Aconcatenated withB), whereAandBare valid strings, or - It can be written as
(A), whereAis 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 <= 1000s[i]is either'('or')'.
Code Examples
#1 Code Example with Java Programming
Code -
Java Programming
class Solution {
public int minAddToMakeValid(String s) {
int count = 0;
Stack < Character> stack = new Stack<>();
for (char c : s.toCharArray()) {
if (c == '(') {
stack.push(c);
} else {
if (stack.isEmpty()) {
count++;
} else {
stack.pop();
}
}
}
return count + stack.size();
}
}
Input
s = "())"
Output
1
#2 Code Example with Javascript Programming
Code -
Javascript Programming
const minAddToMakeValid = function(S) {
if(S === '' || S == null) return 0
const len = S.length
const h = {
o: 0,
c: 0
}
for(let i = 0; i < len; i++) {
if(S[i] === '('> {
h.o++
} else {
if(h.o > 0) {
h.o--
} else {
h.c++
}
}
}
return h.o + h.c
};
Input
s = "())"
Output
1
#3 Code Example with Python Programming
Code -
Python Programming
class Solution:
def minAddToMakeValid(self, S):
r, l = 0, []
for s in S:
if s == "(":
l.append(s)
elif l:
l.pop()
else:
r += 1
return r + len(l)
Input
s = "((("
Output
3
#4 Code Example with C# Programming
Code -
C# Programming
namespace LeetCode
{
public class _0921_MinimumAddToMakeParenthesesValid
{
public int MinAddToMakeValid(string S)
{
var count = 0;
var result = 0;
foreach (var ch in S)
{
if (ch == '(')
count++;
else
{
if (count == 0) result++;
else count--;
}
}
return result + count;
}
}
}
Input
s = "((("
Output
3