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