Stacks: Minimum Insertions to Balance a Parentheses String

Problem Statement:

You are given a string with “(” and “)”. You need to make the string balanced and return the min count.

We consider a string as balanced if for every ‘(‘, there is corresponding ‘))’

Example

Input: s = “(()))”
Output: 1

For the second ‘(‘ we have 2 ‘))’.

But for the first ‘(‘ we have only 1 ‘)’

Solution

We will use stack for the solution.

Whenever we encounter an “(” we push it into the stack.

When we encounter “)”, we will check in the string, if we have two “)” or only one “)”.

Then we update the count appropriately.

Then we check if the stack is not empty, then we pop the “(“, as we have calculated the count in the previous if case.

Then while returning from the function, we will check if we have additional “(“, it means that we need to add additional two “)”.

Solution in C++

#include <algorithm>  
#include <iostream>    
#include <string>
#include <stack>
#include <vector>
#include <unordered_map> 

using namespace std;


int minInsertions(string s) 
{
    int count = 0, n = s.length();
    stack<char> st;

    for (int i = 0; i < n; i++) 
    {
        if (s[i] == '(') st.push(s[i]);
        else 
        {
            // If we have both )) in the string, increment i and if we have a single ) increase count
            if (i + 1 < n && s[i] == s[i + 1]) 
                i++;
            else 
                count++;
            
            // If we have ( for corresponding )), pop otherwise increase the count.
            if (!st.empty()) 
                st.pop();
            else 
                count++;
        }
    }
    
    return count + st.size() * 2;
}
int main()
{
    cout<<"The min insertion required are "<<minInsertions("(()))");

    return 0;
}

Output:

The min insertion required are 1