×

String Coding Problems

Arrays Coding Problems

Sorting Coding Problems

Searching Coding Problems

Coding Algorithms

Tree Coding Problems

Stack Coding Problems

Linked list Coding Problems

Graph Coding Problems

Greedy Algorithms Coding Problems

Dynamic Programming Coding Problems

Matrix Coding Problems

Recursion Coding Problems

Number Theory Coding Problems

Backtracking Coding Problems

Heap Coding Problems

Brute Force Coding Problems

Implementation Coding Problems

Google Contests

Competitive Programming Coding

Miscellaneous

Minimum Add to Make Parentheses Valid

Minimum Add to Make Parentheses Valid: Here, we are going to learn how to find a minimum number of insertions to convert a string into a valid parenthesis? It can be featured in any interview rounds.
Submitted by Radib Kar, on June 14, 2020

Problem statement

Given a string S consisting only of '(' and ')' parentheses, we add the minimum number of parentheses '(' or ')' in any positions so that the resulting parentheses string is valid.
Formally, a parentheses string is valid if and only if:

  • It is the empty string, or
  • It can be written as AB (A concatenated with B), where A and B are valid strings, or
  • It can be written as (A), where A is a valid string.

Given a parentheses string, return the minimum number of parentheses we must add to make the resulting string valid.

Input

An invalid/valid parenthesis string.

Output

Minimum number of brackets to be added so that it becomes valid.

Example

Example 1:
Input:
"())"

Output: 
Minimum number of brackets to be added is 1 
(valid parenthesis would be "(())"

Example 2:
Input: 
"((("

Output: 
Minimum number of brackets to be added is 3 
(valid parenthesis would be "((()))"

Example 3:
Input: 
"()"

Output: 
Minimum number of brackets to be added is 0 
(Already a valid parenthesis)

Example 4:
Input: 
"()))(("

Output: 
Minimum number of brackets to be added is 4 
(valid parenthesis would be "()()()(())"

Explanation and solution approach

Let's discuss the last example which pretty much covers the other cases as well. The thing to note is we can only add, we can't delete. So, we need to insert the corresponding bracket whenever there is a violation. We can track the violation using stack similar way we check for valid parenthesis.

The algorithm will be like follow,

  1. Create a stack to store characters, stack<char> st;
  2. Initialize the count of minimum numbers to be added, count=0;
  3. for i=0 to s.length()-1
        if(s[i]  is  opening bracket )
            push to stack
        else{ //s[i] is closing bracket
            if stack is empty{
                increment count as its a violation
                continue;
            }
            else if(s[i] is closing bracket but the stack top is not opening bracket){
                // it's a violation and increment count;               
                st.pop();
            }
        }
    
  4. If there is still some opening brackets left in the stack they needs to be paired as well, so
    count=count+stack size;
    
    Stack size may be zero too
    Count gives the final result

Now let's execute for our example,

String s="()))(("
Initially count=0
Stack is empty

i=0
s[i]=('
push to stack
stack
--------
 (
--------
Count=0

i=1
s[i]=')'
s[i] correctly pairs with top of stack
pop from stack
stack is empty now
--------

--------
Count=0


i=2
s[i]=')'
stack is empty, nothing to pair, 
it's a violation and we need to add '(' here
--------

--------
increment count
Count=1

i=3
s[i]=')'
stack is empty, nothing to pair, 
it's a violation again and we need to add '(' here
--------

--------
increment count
Count=2


i=4
s[i]=('
push to stack
stack
--------
(
--------
Count=2

i=5
s[i]=('
push to stack
stack
--------
(
--------
(
--------
Count=2

That's end the loop

Out of the loop stack is not empty 
and we need to add two closing brackets 
to pair up those remaining open brackets

Hence, count = count + stack size = 4

That's the final result

C++ Implementation

#include <bits/stdc++.h>
using namespace std;

int minAddToMakeValid(string s)
{
    stack<char> st;
    int count = 0;
    for (int i = 0; i < s.length(); i++) {
        if (s[i] == '(')
            st.push(s[i]);
        else {
            if (st.empty()) {
                count++;
                continue;
            }

            else if (s[i] == ')' && st.top() != '(')
                count++;

            st.pop();
        }
    }

    count += st.size();

    return count;
}

int main()
{
    string s;
    cout << "Enter the parenthesis string\n";
    cin >> s;
 
    cout << "Minimum brackets to add: " << minAddToMakeValid(s) << endl;

    return 0;
}

Output

RUN 1:
Enter the parenthesis string
(())))((
Minimum brackets to add: 4

RUN 2:
Enter the parenthesis string
()(((((((((()
Minimum brackets to add: 9


Comments and Discussions!

Load comments ↻





Copyright © 2024 www.includehelp.com. All rights reserved.