[C++] Array-based, Less-than-2-pass Solution Explained, ~100% Time, ~90% Space
So, the problem of the valid parentheses is a classic declined in several variations - like this one that has filler characters - nothing too complex, but still
So, the problem of the valid parentheses is a classic declined in several variations - like this one that has filler characters - nothing too complex, but still a minor hindrance to consider.\n\nTo solve this problem, we will first of all declare a few support variables:\n* `tmp` is an array of chars, with the same size of `s`;\n* `p` will count how many parentheses we opened, while `pos` will be the pointer we will use to work on `tmp` - both will be set to `0`.\n\nIn our first pass through all the characters in the input string, we will have 3 base case:\n* `c == \'(\'` will make it add to `tmp` (and increase `pos`), on top of increasing the dedicated `p` counter;\n* `c == \')\'` will add the character to `tmp` only if `p > 0` and we will do nothing otherwise (ie: the character is ignored);\n* we will add any other character to `tmp`.\n\nOnce done, we will have stored `pos` character to compose a new, filtered string; but we might also have potentially `p` open parentheses that need to be removed.\n\nTo do so, we will generate out result variable `res` to be `pos - p` characters long and then proceed to fill it from the right, always adding each character that is not an opened parentheses, decreasing `p` otherwise and actually adding `\'(\'` only after `p` is `<= 0` - meaning we got rid of the extra `p` open parentheses we collected before (whereas we can be sure that `tmp` will never have any extra closed parentheses).\n\nOnce done, we can return `res` :)\n\nThe code:\n\n```cpp\nclass Solution {\npublic:\n    string minRemoveToMakeValid(string &s) {\n        // support variables\n        char tmp[s.size()];\n        int p = 0, pos = 0;\n        for (char c: s) {\n            switch(c) {\n                case \'(\':\n                    p++;\n                    tmp[pos++] = c;\n                    break;\n                case \')\':\n                    // inserting closing parentheses only with p > 0\n                    if (p > 0) {\n                        p--;\n                    }\n                    else break;\n                default:\n                    tmp[pos++] = c;\n            }\n        }\n        // properly sizing res\n        string res(pos - p, \'*\');\n        for (int i = pos - 1, j = pos - p - 1; i >= 0; i--) {\n            if (tmp[i] != \'(\' || p-- <= 0) res[j--] = tmp[i];\n        }\n        return res;\n    }\n};\n```\n\nWant to save even more memory? Okay, then overwrite directly `s`:\n\n```cpp\nclass Solution {\npublic:\n    string minRemoveToMakeValid(string &s) {\n        // support variables\n        char tmp[s.size()];\n        int p = 0, pos = 0;\n        for (char c: s) {\n            switch(c) {\n                case \'(\':\n                    p++;\n                    tmp[pos++] = c;\n                    break;\n                case \')\':\n                    // inserting closing parentheses only with p > 0\n                    if (p > 0) {\n                        p--;\n                    }\n                    else break;\n                default:\n                    tmp[pos++] = c;\n            }\n        }\n        // properly sizing s\n        s.resize(pos - p);\n        for (int i = pos - 1, j = pos - p - 1; i >= 0; i--) {\n            if (tmp[i] != \'(\' || p-- <= 0) s[j--] = tmp[i];\n        }\n        return s;\n    }\n};\n```
['String', 'C', 'C++']