# 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:**‘),’ ‘},’ ‘].’** A **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

**What is a stack?**

A__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.

**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.

**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.

**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 Parentheses__, __Generate all parentheses__, __Different 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!

Comments

## No comments yet

## Be the first to share what you think