Coderust: Hacking the Coding Interview/

...

/

Minimum Remove to Make Valid Parentheses

Minimum Remove to Make Valid Parentheses

Remove the minimum number of parentheses, leaving matching parentheses in the input string.

We'll cover the following...

Statement

Given a string with matched and unmatched parentheses, remove the minimum number of parentheses with all matching parentheses in the string.

Example

Sample input

str = "ab)cca(spo)(sc(s)("

Expected output

"abcca(spo)sc(s)"

Try it yourself

#include <iostream>
using namespace std;
string MinRemoveParentheses(string s) {
	// write your code here
	return "";
}

Solution

We’ll traverse the array to:

  1. Check whether a delimiter is unmatched or not.
  2. Note the index of the unmatched delimiter so that we can remove them later on.

To do this, we go over each character one by one. If the character is a delimiter, we push it and its index in the stack; otherwise, we move on to the next character. To check whether the delimiter is matched or not, we make the following check at each character:

If the current character is an ending delimiter and the character at the top of the stack is a starting one, then both of them are matched.

In such a case, we do not add the current ...

Access this course and 1400+ top-rated courses and projects.