\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 stack = new Stack<>();\n for(int i=0;i set = new HashSet<>(stack);\n for(int i=0;i 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 : \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 A not so contant solution : [ `used a char [] ` ]\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) {\n R.append(ch);\n close++;\n }\n else {\n open = open < 0 ? 0 : open--;\n }\n }\n }\n\n // remove invalid open parenthesis\n s = R.toString();\n int n = s.length();\n R.setLength(0);\n open = close = 0;\n char[] A = s.toCharArray();\n \n for(int i=n-1;i>=0;i--) {\n char ch = s.charAt(i);\n if(Character.isAlphabetic(ch)) {\n continue;\n }\n else if(ch == \')\') {\n close++;\n }\n else {\n if(close > open) {\n open++;\n }\n else {\n A[i] = \'*\';\n close = close < 0 ? 0 : close--;\n }\n }\n }\n \n for(char ch : A) \n if(ch!=\'*\')\n R.append(ch);\n \n return R.toString();\n }\n}\n```

Minimum Remove to Make Valid Parentheses

Problem Description

Problem Description

Answer Panel