921. Minimum Add to Make Parentheses Valid LeetCode Solution
In this guide, you will get 921. Minimum Add to Make Parentheses Valid LeetCode Solution with the best time and space complexity. The solution to Minimum Add to Make Parentheses Valid problem is provided in various programming languages like C++, Java, and Python. This will be helpful for you if you are preparing for placements, hackathons, interviews, or practice purposes. The solutions provided here are very easy to follow and include detailed explanations.
Problem Statement of 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 (A concatenated with B), where A and B are valid strings, or
It can be written as (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.
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 ')'.
Complexity Analysis
Time Complexity: O(n)
Space Complexity: O(1)
921. Minimum Add to Make Parentheses Valid LeetCode Solution in C++
class Solution {
public:
int minAddToMakeValid(string s) {
int l = 0;
int r = 0;
for (const char c : s)
if (c == '(') {
++l;
} else {
if (l == 0)
++r;
else
--l;
}
return l + r;
}
}; /* code provided by PROGIEZ */
921. Minimum Add to Make Parentheses Valid LeetCode Solution in Java
class Solution {
public int minAddToMakeValid(String s) {
int l = 0;
int r = 0;
for (final char c : s.toCharArray())
if (c == '(') {
++l;
} else {
if (l == 0)
++r;
else
--l;
}
return l + r;
}
} // code provided by PROGIEZ
921. Minimum Add to Make Parentheses Valid LeetCode Solution in Python
class Solution:
def minAddToMakeValid(self, s: str) -> int:
l = 0
r = 0
for c in s:
if c == '(':
l += 1
else:
if l == 0:
r += 1
else:
l -= 1
return l + r # code by PROGIEZ
