Parentheses problems
3 min readAug 14, 2020
To be added
921. Minimum Add to Make Parentheses Valid
class Solution {
public:
int minAddToMakeValid(string S) {
int ret = 0, right = 0;
for (auto& c : S)
{
if (c == '(')
{
right += 1;
}
else
{
if (right == 0)ret++;
else right--;
}
}
return ret + right;
}
};1541. Minimum Insertions to Balance a Parentheses String
stack-based solution
class Solution {
public:
int minInsertions(string s) {
stack<char> stack;
int ret = 0;
for (auto c : s)
{
if (stack.empty())
{
stack.push(c);continue;
}
// case 1: "))"
if (c==')' && stack.top() == ')')
{
stack.pop();
//case of "))"
if(stack.empty())
{
ret += 1;
continue;
}
// case of "())"
else
{
stack.pop();
}
}
// case 2: "()"
else if (c==')' && stack.top() == '(')
{
stack.push(c);
}
// case 3: "(("
else if (c=='(' && stack.top() == '(')
{
stack.push(c);
}
// case 4: ")("
else if (c=='(' && stack.top() == ')')
{
stack.pop();
if(stack.empty())
{
ret += 2;
stack.push(c);
continue;
}
else
{
stack.pop();
ret += 1;
stack.push(c);
continue;
}
}
}
if(!stack.empty() && stack.top()==')')
{
stack.pop();
//case of ")"
if(stack.empty())ret += 2;
//case of "()"
else
{
ret += 1;
//stack.pop();
stack.pop();
}
}
ret += 2*stack.size();
return ret;
}
};Greedy based solution
The explanation is from HERE
A brief explanation.. what I understood here..res denotes number of left/right parenthesis needed which is already added.
right denotes number of right parenthesis needed.Example 1: Consider ((()(,n= 5 ,i=0,1...4
i=0, we have ( it means we need two right parenthesis (they are in pair) so.. right+=2 => res =0, right =2
i=1, again we have ( it means we need two right parenthesis (they are in pair) so.. right+=2 => res =0, right =4
i=2, again we have ( it means we need two right parenthesis (they are in pair) so.. right+=2 => res =0, right =6
i=3, we have ) we subtract one from right. so.. right-- => res =0, right =5
i=4, we have ( but here right is odd so we need to make it even with right-- and increment res++ => res =1, right =4. Also, as we have got a left parenthesis then we need two right parenthesis (they are in pair) so.. right+=2 => res =1, right =6finally ans is res + right => 1 +6 == 7Example 2: )))()
Similarly, we can see when we have right<0 then we increment res by one & add 2 to right as they should be in pairs..
Solution
class Solution {
public:
int minInsertions(string s)
{
// ret means added element, right means how many right parentheses are needed.
int ret = 0, right = 0;
for (auto& c : s)
{
if (c == '(')
{
// if not even, make it even by adding one right parenthese
if (right&1)
{
ret++;
right--;
}
// since current is '(', we need 2 right parenthese tp match the current one.
right += 2;
}
else // right parentheses
{
// we have a right, the needed will be reduced by 1.
right--;
// if we have too many right parenthese, we need add one left parenthese
if(right < 0)
{
ret++;
right += 2;
}
}
}
return ret + right;
}
};
