LC 1249. Minimum Remove to Make Valid Parentheses

Sarthak Sehgal · March 20, 2020

medium   strings

Solution

Try solving 921. Minimum Add to Make Parentheses Valid for better understanding. Our approach is to identify the positions (index) of invalid parenthesis and store them in a vector. Then, we will traverse through the string once again and only add the characters at index not matching with the invalid parenthesis positions to our answer string. Let’s say we keep track of number of “net” open parenthesis. That is, we increment the count whenever we encounter ( and decrement the count whenever we encounter ) but we don’t let the count fall below 0. Then, a parenthesis can be invalid if:

  1. There is a closing parenthesis when open parenthesis count is 0. For example, the first two parenthesis in the string ))() are invalid.
  2. We have traversed the whole string but open parenthesis count is still > 0. This means that there is no matching closing parenthesis for these. For example, the last two parenthesis in the string ()(( are invalid.

With the same idea, we keep track of open parenthesis positions in a vector called open. We also keep a vector toRemove which stores the index of invalid parenthesis. Consider the following cases while traversing through string:

  1. (: open.push_back(position)
  2. ):
    • open.size() > 0: open.pop_back => this is a matching closing bracket
    • open.size() == 0: toRemove.push_back(position) => no matching open bracket present.

At the end, all the brackets in vector open are unmatched so push the positions to toRemove.

string minRemoveToMakeValid(string s) {
    vector<int> toRemove;
    vector<int> open;
    string ans = "";
    
    for (int i=0; i<s.length(); i++) {
        char c = s[i];
        
        if (c!='(' && c!=')')
            continue;
        if (c=='(')
            open.push_back(i);
        if (c==')')
            if (!open.empty())
                open.pop_back();
            else
                toRemove.push_back(i);
    }
    for (int i=0; i<open.size(); i++)
        toRemove.push_back(open[i]);
    
    for (int i=0, j=0; i<s.length(); i++) {
        if (j<toRemove.size() && i==toRemove[j]) {
            j++;
            continue;
        }
        ans += s[i];
    }
    
    return ans;
}

Time complexity: O(n)
Space complexity: O(n)

Note that we could have employed an approach to remove the invalid bracket as we encounter it using substr function but time taken by substr is not O(1) so the solution would indeed have been O(n^2).

Twitter, Facebook