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