[Java] Clean StringBuilder solution
O(N) Solution:\n\nA pair of parentheses is consist of an open and a close. The open has to be before the close.\nSo, we can remove the extra close parenthese th
**O(N) Solution:**\n\nA pair of parentheses is consist of an open and a close. The open has to be before the close.\nSo, we can remove the extra close parenthese then remove extra open parenthese\n\n the fist iteration, we remove the unwanted )\n the second iteration, we remove the unwanted (\n \n```\npublic String minRemoveToMakeValid(String s) {\n    StringBuilder sb = new StringBuilder();\n    int open = 0;\n    for (char c : s.toCharArray()) {\n        if (c == \'(\') \n            open++;\n        else if (c == \')\') {\n            if (open == 0) continue; // remove invalid close parenthese\n            open--;\n        }\n        sb.append(c);\n    }\n    \n    StringBuilder result = new StringBuilder();\n    for (int i = sb.length() - 1; i >= 0; i--) {\n        if (sb.charAt(i) == \'(\' && open-- > 0) continue; // remove invalid open parenthese\n        result.append(sb.charAt(i));\n    }\n    \n    return result.reverse().toString();\n}\n```\n\n\nCredit to @Sithis and @hamlet_fiis pointing out the time comlexity of `deleteCharAt(i)` being O(N) which makes this a O(N2) solution. \nEdited the code to append all characters except those invalid open parentheses, then reverse the stringbuilder. This will achieve O(N) with slight headache.\nA new `StringBuilder` is created for the result, but you could reuse the first one by replacing the `(` in place and prune the starting `open` number of chars.\n\n**Original O(N2) Solution:**\n\nThe intuition is counting the number of invalid `(` and removing the invalid `)` in the first pass.\nIf there are `open` number of invalid `(` left, we just need to remove them from the end in the second pass.\n\n```\npublic String minRemoveToMakeValid(String s) {\n    StringBuilder sb = new StringBuilder();\n    int open = 0;\n    for (char c : s.toCharArray()) {\n        if (c == \'(\') {\n            open++;\n        } else if (c == \')\') {\n            if (open == 0) continue;\n            open--;\n        }\n        sb.append(c);\n    }\n    \n    for (int i = sb.length() - 1; i >= 0 && open > 0; i--) {\n        if (sb.charAt(i) == \'(\') {\n            sb.deleteCharAt(i);\n            open--;\n        }\n    }\n    \n    return sb.toString();\n}\n```\n
[]