Home »
Interview coding problems/challenges
Minimum Add to Make Parentheses Valid
Minimum Add to Make Parentheses Valid: Here, we are going to learn how to find a minimum number of insertions to convert a string into a valid parenthesis? It can be featured in any interview rounds.
Submitted by Radib Kar, on June 14, 2020
Problem statement:
Given a string S consisting only of '(' and ')' parentheses, we add the minimum number of parentheses '(' or ')' 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 with B), where A and B are valid strings, or
 It can be written as (A), where A is a valid string.
Given a parentheses string, return the minimum number of parentheses we must add to make the resulting string valid.
Input:
An invalid/valid parenthesis string.
Output:
Minimum number of brackets to be added so that it becomes valid.
Example:
Example 1:
Input:
"())"
Output:
Minimum number of brackets to be added is 1
(valid parenthesis would be "(())"
Example 2:
Input:
"((("
Output:
Minimum number of brackets to be added is 3
(valid parenthesis would be "((()))"
Example 3:
Input:
"()"
Output:
Minimum number of brackets to be added is 0
(Already a valid parenthesis)
Example 4:
Input:
"()))(("
Output:
Minimum number of brackets to be added is 4
(valid parenthesis would be "()()()(())"
Explanation and solution approach
Let's discuss the last example which pretty much covers the other cases as well. The thing to note is we can only add, we can't delete. So, we need to insert the corresponding bracket whenever there is a violation. We can track the violation using stack similar way we check for valid parenthesis.
The algorithm will be like follow,
 Create a stack to store characters, stack<char> st;
 Initialize the count of minimum numbers to be added, count=0;

for i=0 to s.length()1
if(s[i] is opening bracket )
push to stack
else{ //s[i] is closing bracket
if stack is empty{
increment count as its a violation
continue;
}
else if(s[i] is closing bracket but the stack top is not opening bracket){
// it's a violation and increment count;
st.pop();
}
}

If there is still some opening brackets left in the stack they needs to be paired as well, so
count=count+stack size;
Stack size may be zero too
Count gives the final result
Now let's execute for our example,
String s="()))(("
Initially count=0
Stack is empty
i=0
s[i]=('
push to stack
stack

(

Count=0
i=1
s[i]=')'
s[i] correctly pairs with top of stack
pop from stack
stack is empty now


Count=0
i=2
s[i]=')'
stack is empty, nothing to pair,
it's a violation and we need to add '(' here


increment count
Count=1
i=3
s[i]=')'
stack is empty, nothing to pair,
it's a violation again and we need to add '(' here


increment count
Count=2
i=4
s[i]=('
push to stack
stack

(

Count=2
i=5
s[i]=('
push to stack
stack

(

(

Count=2
That's end the loop
Out of the loop stack is not empty
and we need to add two closing brackets
to pair up those remaining open brackets
Hence, count = count + stack size = 4
That's the final result
C++ Implementation:
#include <bits/stdc++.h>
using namespace std;
int minAddToMakeValid(string s)
{
stack<char> st;
int count = 0;
for (int i = 0; i < s.length(); i++) {
if (s[i] == '(')
st.push(s[i]);
else {
if (st.empty()) {
count++;
continue;
}
else if (s[i] == ')' && st.top() != '(')
count++;
st.pop();
}
}
count += st.size();
return count;
}
int main()
{
string s;
cout << "Enter the parenthesis string\n";
cin >> s;
cout << "Minimum brackets to add: " << minAddToMakeValid(s) << endl;
return 0;
}
Output:
RUN 1:
Enter the parenthesis string
(())))((
Minimum brackets to add: 4
RUN 2:
Enter the parenthesis string
()(((((((((()
Minimum brackets to add: 9
TOP Interview Coding Problems/Challenges