Minimize the length of a given string by removing subsequences forming valid parenthesis

Introduction

There are two types of parentheses. Open and close parentheses. In this problem, an open parentheses can be like:  ‘(, ‘‘{, ‘‘[, ‘ and closed parentheses can be like:‘),’ ‘},’ ‘].’well-formed parenthesis string is a balanced parenthesis string. A string of parentheses is called balanced if, for every opening bracket, there is a unique closing bracket. If you don’t have any prior knowledge of balanced parentheses, it’s suggested to look up this blog.

In this article, the problem asks to delete all the balanced parentheses from the string and return the minimum length left.

Problem Statement

Given a string, remove all the subsequences which form balanced parentheses and print the remaining characters.

For example: 

INPUT : s= “((){()({})”

OUTPUT:  “({“

Here, the subsequence consisting of s[1], s[2], s[4], s[5], s[6], s[7], s[8], s[9] is ()()({}). Thus, we remove it and the string left is = ({. Thus the output is this. 

INPUT : s= “)()())”

OUTPUT:  “))”

Here, the subsequence consisting of s[1], s[2], s[3], s[4] is ()(). Thus, we remove it and the string left is = )). Thus the output is this. 

Solution Approach

Thinking about the logic of this problem is straightforward. We have to remove the balanced parentheses. And for this, we need to find balanced parentheses and remove them. 

Hint 1:

A valid parenthesis expression has the interesting property that a sub-expression of a valid expression must also be a valid expression. (Not all sub-expression).

For example: Consider a string  { [ [ ] { } ] } ( ) ( )

Hint 2:

What if we simply remove the matching pair of parentheses whenever we come across them in the expression? It would further shorten the expression. 

For example: 

{ { } { ( ) } //remove matching pair 1

  |_|

{ _ _ { ( ) } //remove matching pair 2

          |_|

{ _ _ { _ _ } //remove matching pair 3

        |____|

This is exactly what we will do. We keep pushing the characters of the string into a stack and at the time when the top element of the stack is an opening bracket and the current element is a closing bracket, we pop the top element of the stack as these both are forming a balanced parenthesis. Otherwise, keep pushing elements into the stack. 

Steps are : 

  • Input the string and call the function remove_parenthesis() with the string as a parameter.
  • In the function remove_parenthesis():
    • Declare a stack of characters.
    • Start iterating from i=0 to i<s.length() of the string. 
    • If the current character is an opening bracket, i.e., s[i] ==’(,’ or ‘{’ or ‘[,’ push it into the stack. 
    • Else if s[i]==’),’ or ‘}’ or ‘].’
      • If the stack is empty, push it into the stack.
      • Otherwise, if the top element of the stack is an opening bracket, pop it from the stack and move to the next i. Otherwise, push s[i] into the stack.
      • At this stage, the stack contains the left-out characters. So, just declare an answer string, then add the elements of the stack into it.
      • Since the stack contains elements in reverse order of their occurrence, we need to reverse the answer string. So, reverse the answer string.
      • Return the answer string.
    • Print the returned string.

C++ implementation

Below is the C++ implementation of the above idea.

#include<bits/stdc++.h>
using namespace std;
string remove_parenthesis(string s){ 
   stack<char>stk; // Declare a stack of characters
   //Start iterating from i=0 to i<s.length() of the string.
   for(int i=0;i<s.length();i++){
       // If the stack is empty, push the current character into it
       if(stk.empty()){
           stk.push(s[i]);
       }
       else{
           //If the current character is an opening bracket, i.e; 
           //s[i] ==’(’, or ‘{’ or ‘[’, push it into the stack. 
           if(s[i]=='{' || s[i]=='(' || s[i]=='['){
               stk.push(s[i]);
           }
           //if the top element of the stack is an opening bracket, pop it 
           //from the stack and move to the next i.
           else if(stk.top()=='{' || stk.top()=='(' || stk.top()=='['){
               stk.pop();
           }
           //else push it into the stack
           else{
               stk.push(s[i]);
           }
       }
   }
   // At this stage the stack contains the left out characters. So, just declare
   // an answer string the add the elements of the stack into it.
   string ans;
   while(!stk.empty()){
       ans+=(stk.top());
       stk.pop();
   }
   // Since, the stack contains elements in reverse order of their occurence, 
   // we need to reverse the answer string
   reverse(ans.begin(),ans.end());
   // Return the answer string
   return ans;
}
int main(){
   string s;  // Input the string 
   cin>>s;
   string ans = remove_parenthesis(s);
   cout<<ans<<endl; // Print the answer string
};

Input

((){()({})

Output

({

Complexities

Time complexity

O(n), where n is the length of the input string.

Reason: Because we’re iterating through the whole string once.

Space complexity

O(n), where n is the length of the input string.

Reason: For storing the characters of the string into the stack.

Frequently asked questions

  1. What is a stack?
    stack is an abstract data type that serves as a collection of elements and has two primary operations: Push, which adds an element to the collection, and Pop, which removes the most recently added element that has not yet been removed.
     
  2. What data structure can be used to check if the syntax has balanced parentheses?
    Stack comes in handy to check if the syntax has balanced parentheses.
     
  3. What are balanced parentheses?
    A string of parentheses is intuitively balanced if each left parenthesis has a matching right parenthesis and the matched pairs are well nested.
     
  4. What is stack pop ()?
    Stack pop() removes the most recently added element that has not yet been removed.

Key Takeaways

In this article, we’ve discussed the problem minimize the length of a given string by removing subsequences forming valid parenthesis. There are various problems with strings consisting of parentheses such as Valid ParenthesesGenerate all parenthesesDifferent ways to add parentheses, and Remove invalid parentheses

I would suggest you solve them to gain more confidence on this topic. These questions are asked during various coding contests as well as placements tests.

To practice more such problems, Codestudio is a one-stop destination. This platform will help you acquire effective coding techniques and give you an overview of student interview experience in various product-based companies.

Happy Coding!

Was this article helpful ?
0 upvotes

Comments

No comments yet

Be the first to share what you think