JS, Python, Java, C++ | Stack Solution w/ Explanation | beats 100%
(Note: This is part of a series of Leetcode solution explanations. If you like this solution or find it useful, please upvote this post.)\n\n---\n\nIdea:\n\nVal
*(Note: This is part of a series of Leetcode solution explanations. If you like this solution or find it useful,* ***please upvote*** *this post.)*\n\n---\n\n***Idea:***\n\nValid parentheses follow the **LIFO method** (last in, first out), so we should automatically be thinking of some kind of **stack** solution.\n\nTo 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 **"("**.\n\nNow 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.\n\nThe most effective method varies by language, so I\'ll discuss those in the *Implementation* section.\n\nThen we can make our removals and re-form and **return** our answer.\n\n---\n\n***Implementation:***\n\nJavascript 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.\n\nWhile 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**).\n\nJavascript 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.\n\nJava 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.\n\nOn 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.\n\nFor 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.\n\nSince 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**.\n\nThen, 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.\n\nAt the end, the substring between **0** and **i** will represent the "squeezed" string with all invalid parentheses removed, so we should **return** it.\n\n---\n\n***Javascript Code:***\n\nThe best result for the code below is **76ms / 44.7MB** (beats 100% / 96%).\n```javascript\nvar minRemoveToMakeValid = function(S) {\n    S = S.split("")\n    let len = S.length, stack = []\n    for (let i = 0, c = S[0]; i < len; c = S[++i])\n        if (c === ")")\n            if (stack.length) stack.pop()\n            else delete S[i]\n        else if (c === "(") stack.push(i)\n    for (let i = 0; i < stack.length; i++)\n        delete S[stack[i]]\n    return S.join("")\n};\n```\n\n---\n\n***Python Code:***\n\nThe best result for the code below is **72ms / 15.8MB** (beats 100% / 91%).\n```python\nclass Solution:\n    def minRemoveToMakeValid(self, S: str) -> str:\n        S, stack = list(S), []\n        for i, c in enumerate(S):\n            if c == ")":\n                if stack: stack.pop()\n                else: S[i] = ""\n            elif c == "(": stack.append(i)\n        for i in stack: S[i] = ""\n        return "".join(S)\n```\n\n---\n\n***Java Code:***\n\nThe best result for the code below is **5ms / 39.1MB** (beats 100% / 99%).\n```java\nclass Solution {\n    public String minRemoveToMakeValid(String S) {\n        char[] ans = S.toCharArray();\n        int len = S.length(), stIx = 0, i = 0, j = 0;\n        int[] stack = new int[len+1];\n        for (; i < len; i++)\n            if (ans[i] == \')\')\n                if (stIx > 0) stIx--;\n                else ans[i] = \'_\';\n            else if (ans[i] == \'(\') stack[stIx++] = i;\n        for (i = 0, stack[stIx] = -1, stIx = 0; j < len; j++)\n            if (j == stack[stIx]) stIx++;\n            else if (ans[j] != \'_\') ans[i++] = ans[j];\n        return new String(ans, 0, i);\n    }\n}\n```\n\n---\n\n***C++ Code:***\n\nThe best result for the code below is **16ms / 10.2MB** (beats 99% / 91%).\n```c++\nclass Solution {\npublic:\n    string minRemoveToMakeValid(string S) {\n        int len = S.size(), i = 0, j = 0, stIx = 0;\n        vector<int> stack;\n        for (; i < len; i++)\n            if (S[i] == \')\')\n                if (stack.size() > 0) stack.pop_back();\n                else S[i] = \'_\';\n            else if (S[i] == \'(\') stack.push_back(i);\n        stack.push_back(-1);\n        for (i = 0; j < len; j++)\n            if (j == stack[stIx]) stIx++;\n            else if (S[j] != \'_\') S[i++] = S[j];\n        return S.substr(0, i);\n    }\n};\n```
['C', 'Python', 'Java', 'JavaScript']