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,

1. Create a stack to store characters, stack<char> st;
2. Initialize the count of minimum numbers to be added, count=0;

3. 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();
           }
       }
   

4. 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