Search⌘ K
Home
Courses
Coderust: Hacking the Coding Interview

Minimum Remove to Make Valid Parentheses

Explore how to process strings with unmatched parentheses by removing the minimum number needed to create valid pairs. Understand how to use stacks to track delimiters, identify unmatched parentheses, and reconstruct the valid string. This lesson helps you master an essential technique for solving common coding interview problems efficiently.

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 character to the stack, and we also pop an element from the stack to remove the starting ...