Solution: Minimum Remove to Make Valid Parentheses

This is part of a series of Leetcode solution explanations (index). If you liked this solution or found it useful, please like this post and/or upvote my solution post on Leetcode's forums.

---

Leetcode Problem #1249 (Medium): Minimum Remove to Make Valid Parentheses

---

Description:

Given a string s of '(' , ')' and lowercase English characters.

Your task is to remove the minimum number of parentheses ('(' or ')', in any positions) so that the resulting parentheses string is valid and return any valid string.

Formally, a parentheses string is valid if and only if:

• It is the empty string, contains only lowercase characters, or
• It can be written as AB (A concatenated with B), where A and B are valid strings, or
• It can be written as (A), where A is a valid string.

---

Examples:

Example 1:
Input:	s = "lee(t(c)o)de)"
Output:	"lee(t(c)o)de"
Explanation:	"lee(t(co)de)" , "lee(t(c)ode)" would also be accepted.

Example 2:
Input:	s = "a)b(c)d"
Output:	"ab(c)d"

Example 3:
Input:	s = "))(("
Output:	""
Explanation:	An empty string is also valid.

Example 4:
Input:	s = "(a(b(c)d)"
Output:	"a(b(c)d)"

---

Constraints:

• 1 <= s.length <= 10^5
• s[i] is one of '(' , ')' and lowercase English letters.

---

Idea:

Valid parentheses follow the LIFO method (last in, first out), so we should automatically be thinking of some kind of stack solution.

To check for valid parentheses, you push any "(" onto stack, then pop off the top stack element every time you find a matching ")". If you find a ")" when stack is empty, that ")" must be invalid. At the end of S, any leftover "("'s left in stack must be invalid, as well. Since we'll want to remove those "("'s by index at the end, stack should contain said indexes, rather than just the "(".

Now that we've identified all the invalid parentheses, that leaves us with the problem of removing them from S. We could perform a lot of string slices and copies, but those are typically very slow and memory intensive, so we should probably find a data type that can be directly modified by index access and use that as an intermediary.

The most effective method varies by language, so I'll discuss those in the Implementation section.

Then we can make our removals and re-form and return our answer.

---

Implementation:

Javascript has basic arrays, Python has lists, and Java has char arrays that will perform the job of a more flexible data type for this problem. C++ alone of the four languages has mutable strings, so we can just leave S as is.

While Java has stack/deque/list structures, they're not always terribly efficient, so we can just use a more basic int[] with a length fixed to the size of S, along with an index variable (stIx).

Javascript conveniently allows us to directly delete an array element without screwing up our iteration, so we can use that on the initial pass for invalid "("'s. Python can't do that, but we can easily replace each character we want to delete with an empty string, which effectively does the same thing once the string has been joined again.

Java and C++ won't allow us to replace characters with empty strings, so we can just mark those characters with a character mask for later removal.

On the second pass through Javascript and Python can just repeat the same method while going through the remaining stack. Python is very fast with its appends and pops, so we can use that to our advantage.

For Java and C++, things are more difficult. We can't change the length of the intermediary, but we can alter its contents by index assignment. That means we can use a two-pointer approach to rewrite the beginning portion of the intermediary before ultimately returning a subsection of it.

Since we want to iterate through stack in opposite order (FIFO) this time, we can just tag a -1 onto the end of the stack to avoid issues with going out-of-bounds, and then use stIx starting at 0.

Then, for every iteration, j will increment, but i will only increment if it's not a character we want to remove (either by matching the character mask or the next stack entry), and we'll overwrite the intermediary at i with j's value.

At the end, the substring between 0 and i will represent the "squeezed" string with all invalid parentheses removed, so we should return it.

---

Javascript Code:

var minRemoveToMakeValid = function(S) {
    S = S.split("")
    let len = S.length, stack = []
    for (let i = 0, c = S[0]; i < len; c = S[++i])
        if (c === ")")
            if (stack.length) stack.pop()
            else delete S[i]
        else if (c === "(") stack.push(i)
    for (let i = 0; i < stack.length; i++)
        delete S[stack[i]]
    return S.join("")
};

---

Python Code:

class Solution:
    def minRemoveToMakeValid(self, S: str) -> str:
        S, stack = list(S), []
        for i, c in enumerate(S):
            if c == ")":
                if stack: stack.pop()
                else: S[i] = ""
            elif c == "(": stack.append(i)
        for i in stack: S[i] = ""
        return "".join(S)

---

Java Code:

class Solution {
    public String minRemoveToMakeValid(String S) {
        char[] ans = S.toCharArray();
        int len = S.length(), stIx = 0, i = 0, j = 0;
        int[] stack = new int[len+1];
        for (; i < len; i++)
            if (ans[i] == ')')
                if (stIx > 0) stIx--;
                else ans[i] = '_';
            else if (ans[i] == '(') stack[stIx++] = i;
        for (i = 0, stack[stIx] = -1, stIx = 0; j < len; j++)
            if (j == stack[stIx]) stIx++;
            else if (ans[j] != '_') ans[i++] = ans[j];
        return new String(ans, 0, i);
    }
}

---

C++ Code:

class Solution {
public:
    string minRemoveToMakeValid(string S) {
        int len = S.size(), i = 0, j = 0, stIx = 0;
        vector<int> stack;
        for (; i < len; i++)
            if (S[i] == ')')
                if (stack.size() > 0) stack.pop_back();
                else S[i] = '_';
            else if (S[i] == '(') stack.push_back(i);
        stack.push_back(-1);
        for (i = 0; j < len; j++)
            if (j == stack[stIx]) stIx++;
            else if (S[j] != '_') S[i++] = S[j];
        return S.substr(0, i);
    }
};

Comments

[Joy👨🏻‍💻🚀]

var minRemoveToMakeValid = function(s) {
let words = s.split("");
let open = [];
let closed = [];
for(let i=0;i let c=words[i];
if(c===")") {
closed.push(i);
if(closed.length > open.length) {
closed.pop();
delete words[i];
}

   } else if(c==="(") {
       open.push(i)
   }

}
while(open.length > closed.length) {
let position = open.pop();
delete words[position];
}

return words.join("");
};