Java, two scans, no stack, explained
We can find invalid paretheses in two scans - first one from left to right we\'re finding ")" without proper opening "(", remove those immidiately. On the secon
We can find invalid paretheses in two scans - first one from left to right we\'re finding ")" without proper opening "(", remove those immidiately. On the second pass go from right to left and search for invalid "(" without proper ")". \nAs we need to return string we already have to create a new DS to store that result. It\'s possible to use StringBuilder to append and remove characters.\nO(n) time - two string scans. O(n) space - need a StringBuilder of length up to n.\n\n```\n    public String minRemoveToMakeValid(String s) {\n        StringBuilder sb = new StringBuilder();\n        int c = 0;\n        for (char ch : s.toCharArray()) {\n            if (ch == \')\') {\n                if (c == 0) continue;\n                --c;\n            }\n            else if (ch == \'(\') ++c;\n            sb.append(ch);\n        }\n        c = 0; int i = sb.length();\n        while (--i >= 0) {\n            if (sb.charAt(i) == \')\') ++c;\n            else if (sb.charAt(i) == \'(\') {\n                if (c == 0) {\n                    sb.deleteCharAt(i);\n                    continue;\n                }\n                --c;\n            } \n        }\n        return sb.toString();\n    }\n```
['String', 'Java']