📌 [Java] 4 Solutions with slight optimisations
\uD83D\uDCCE A similar question to this is :\n\nMin swaps to make string balanced\n\n*\n\n\u2318 Given statement : \n Your task is to remove the minimum number 
\uD83D\uDCCE A similar question to this is :\n\n[Min swaps to make string balanced](https://leetcode.com/problems/minimum-number-of-swaps-to-make-the-string-balanced/discuss/1676045/Java-4-Solutions-or-Intuition-or-O(n)-or-O(1)-Solutions)\n\n****\n\n\u2318 Given statement : \n* Your task is to remove the minimum number of parentheses.\n* return any valid string.\n\n\u2318 Observations : \n\nIt is quite obvious to get a hunch of using stack when we see a parenthesis problem but we can for sure optimise the space in such a case where the input is limited. [ eg: `here s[i] is either\'(\' , \')\', or lowercase English letter` ].\n\n****\n# Solution 1 : Stack\n```\nclass Solution {\n    public String minRemoveToMakeValid(String s) {\n        Stack<Integer> stack = new Stack<>();\n        for(int i=0;i<s.length();i++) {\n            char ch = s.charAt(i);\n            if(Character.isAlphabetic(ch))\n                continue;\n            if(ch == \'(\')\n                stack.push(i);\n            else {\n                if(!stack.isEmpty() && s.charAt(stack.peek()) == \'(\')\n                    stack.pop();\n                else stack.push(i);\n            }\n        }\n        \n        // if(stack.size() == 0) return "";\n        \n        StringBuilder result = new StringBuilder();\n        HashSet<Integer> set = new HashSet<>(stack);\n        for(int i=0;i<s.length();i++)\n            if(!set.contains(i))\n                result.append(s.charAt(i));\n        \n        return result.toString();\n    }\n}\n```\n\n****\n# Solution 2 : Using Deque\n```\nclass Solution {\n    public String minRemoveToMakeValid(String s) {\n\t\tif (s == null || s.length() == 0) {\n            return s;\n        }\n        \n        char[] chars = s.toCharArray();\n        Deque<Integer> deque = new ArrayDeque<>();\n\t\t\n\t\t// push invalid indices in deque\n        for (int i = 0; i < chars.length; i++) {\n            char c = chars[i];\n            if (c == \'(\') {\n                deque.push(i);\n            } else if (c == \')\') {\n                if (deque.isEmpty()) {\n                    chars[i] = \'#\';\n                } else {\n                    deque.pop();\n                }\n            } \n        }\n        // mark invalid indices\n        while (!deque.isEmpty()) {\n            chars[deque.pop()] = \'#\';\n        }\n        \n        StringBuilder ans = new StringBuilder();\n        for (char c : chars) {\n            if (c != \'#\') {\n                ans.append(c);\n            }\n        }\n        return ans.toString();\n    }\n}\n```\n\n# Constant Solutions : [ Naive -> Optimal ]\n\u2318 Constant Solution 1 : [ ` Slow as we are using insert() function ` ]\n\n\u2714\uFE0F Logic : [ `2 steps` ]\n * remove invalid close parenthesis\n * remove invalid open parenthesis\n\n```\nclass Solution {\n    public String minRemoveToMakeValid(String s) {\n        StringBuilder R = new StringBuilder();\n        int open = 0, close = 0;\n        \n        // remove invalid close parenthesis\n        for(char ch : s.toCharArray()) {\n            if(Character.isAlphabetic(ch)) {\n                R.append(ch);\n            }\n            else if(ch==\'(\') {\n                open++;\n                R.append(ch);\n            }\n            else {\n                if(open > close) { // if there is an \'(\' to be considered for a valid pair\n                    R.append(ch);\n                    close++;\n                }\n                else {\n                    open = open < 0 ? 0 : open--;\n                }\n            }\n        }\n\n        s = R.toString();\n        R.setLength(0); // reset ans\n        int n = s.length();\n        open = close = 0;\n\t\t\n\t\t// remove invalid open parenthesis\n\t\t\n        for(int i=n-1;i>=0;i--) {\n            char ch = s.charAt(i);\n            if(Character.isAlphabetic(ch)) {\n                R.insert(0, ch);\n            }\n            else if(ch == \')\') {\n                R.insert(0, ch);\n                close++;\n            }\n            else {\n                if(close > open) {\n                    R.insert(0, ch);\n                    open++;\n                }\n                else {\n                    close = close < 0 ? 0 : close--;\n                }\n            }\n        }        \n        return R.toString();\n    }\n}\n```\n****\n\n\u2318 Optimal / Refactored Code : \n```\nclass Solution {\n    public String minRemoveToMakeValid(String s) {\n        int n = s.length();\n        StringBuilder ans = removeInvalid(s, \'(\' , \')\');\n        ans = removeInvalid(ans.reverse(), \')\', \'(\');\n        return ans.reverse().toString();\n    }\n    \n    private StringBuilder removeInvalid(CharSequence s, char open_char, char close_char) {\n        StringBuilder answer = new StringBuilder();\n        int open = 0, close = 0, n = s.length();\n        for(int i=0;i<n;i++) {\n            char ch = s.charAt(i);\n            if(Character.isAlphabetic(ch)) answer.append(ch);\n            else if(ch == open_char) {\n                open++;\n                answer.append(ch);\n            }\n            else {\n                if(open > close) {\n                    open--; // found a pair\n                    answer.append(ch);\n                } else {\n                    // we did not find a ( to pair with )\n                }\n            }\n        }\n        return answer;\n    }\n}\n```
['Stack', 'Queue', 'Java']