Greedy: Add minimum to make parentheses valid.

Problem Statement:

You are given a string of ‘(‘ and ‘)’.

You need to return the minimum number of parentheses to make the string valid.

Example

Input: “())”
Output: 1

Solution

Solution is simple.

We take 2 variables,
“open” will represent ‘(‘ to add it to left.
“close” will represent ‘)’ to add it to right.

Then we loop the string, for every c in s

if (c == ‘(‘), we increment close,
if (c == ‘)’), we decrement close.

If ‘close’ is zero, then we increment “open”

Finally we return “open + close”

Solution in C++

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

using namespace std;

 int min_add_to_make_valid(string S) 
 {
     int open = 0, close = 0;
     for (char c : S)
         if (c == '(')
             close++;
         else if (close > 0)
             close--;
         else
             open++;
     return open + close;
 }
int main()
{
   string S = "())";

    cout<<"The min add to make string valid is "<< min_add_to_make_valid(S)<<endl;
    return 0;
}

Output:

The min add to make string valid is 1

 

 

 

 

Write a Comment

Leave a Comment

Your email address will not be published. Required fields are marked *