Minimum Remove to Make Valid Parentheses

Problem

Given a string of characters with parentheses ’(’ and ’)’, find the minimum of parentheses required to remove in order to make the string balanced. Return the balanced string.

A balanced string is such a string where -

• an opening parenthesis ’(’ has a corresponding closing parethesis ’)’ or,
• an empty string.

Examples

Input: “abc(d(e)”
Output: “abcd(e)” or “abc(de)”

Input: “Hello World!”
Output: “Hello World!”
Explanation: A string without any parenthesis is also a balanced string.

Input: ”))(((”
Output: ""
Explanation: An empty string is also a balanced string.

Solution

Using Stack

For an invalid string there could be three cases at each character:

• It is an extra opening parenthesis
• It is an extra closing parenthesis
• It is a valid character

We can check them using a stack.

• Iterate through the characters -

  • If a character is an opening parenthesis, push the index to the stack

  • If it is a closing parenthesis -

    • Check if the stack is empty, if it is not empty (valid character), pop the last item from the stack
    • Else, this index (closing parenthesis) is invalid, we will mark the position in the string as #
• If the stack is not empty, the stack contains the position of the invalid opening parentheses, we will mark those as # in the string.
• In the end, remove those # marked characters.

string minRemoveToMakeValid(string s) {
    stack<int>openingIndex;
    for (int i = 0; i < (int)s.length(); ++i) {
        if (s[i] == '(') {
            openingIndex.push(i);
        } else if (s[i] == ')') {
            if (!openingIndex.empty()) {
                openingIndex.pop();
            } else {
                // extra closing parenthesis
                s[i] = '#';
            }
        }
    }
    // extra opening parentheses
    while(!openingIndex.empty()) {
        s[openingIndex.top()] = '#';
        openingIndex.pop();
    }
    s.erase(remove(s.begin(), s.end(), '#'), s.end());
    return s;
}

Time Complexity: $O(n)$, where $n$ is the length of the string, as we have to iterate through all the characters.

Space Complexity: $O(n)$, where $n$ is the length of the string, for the required stack.

Using Count Variables to Check Balance

Two variables openingCount and closingCount are maintained to count the opening and closing parentheses. We can use different conditions to check if a parenthesis is a valid one or not.

string minRemoveToMakeValid(string s) {
    int openingCount = 0, cur = 0;
    int closingCount = count(s.begin(), s.end(), ')');
    for (int i = 0; i < (int)s.length(); i++) {
        if (s[i] == '(') {
            // increment openingCount for an upcoming closing parenthesis
            ++openingCount;
            // a closing parenthesis exists, thus this is a valid
            // opening parenthesis
            if (closingCount > 0) {
                --closingCount;
            } else {
                continue;
            }
        } else if (s[i] == ')') {
            // an opening parenthesis exists for a closing parenthesis,
            // thus valid opening parentheis
            if (openingCount > 0) {
                --openingCount;
            } else {
                --closingCount;
                continue;
            }
        }
        // including the valid character to the string
        s[cur] = s[i];
        ++cur;
    }
    // remove everything from cur to the end
    s.erase(cur);
    return s;
}

Time Complexity: $O(n)$, where $n$ is the length of the string, as we have to iterate through all the characters.

Space Complexity: $O(1)$