JAVA Solution Explained in HINDI(4 Approaches)
https://youtu.be/UwIcJm_-9L8\n\nFor explanation, please watch the above video and do like, share and subscribe the channel. \u2764\uFE0F Also, please do upvote 
https://youtu.be/UwIcJm_-9L8\n\nFor explanation, please watch the above video and do like, share and subscribe the channel. \u2764\uFE0F Also, please do upvote the solution if you liked it.\n\nSubscribe link:- [ReelCoding](https://www.youtube.com/@reelcoding?sub_confirmation=1)\n\nSubscribe Goal:- 300\nCurrent Subscriber:- 293\n\n# Approach 1\n<!-- Describe your approach to solving the problem. -->\n\n# Complexity\n- Time complexity: O(n)\n<!-- Add your time complexity here, e.g. $$O(n)$$ -->\n\n- Space complexity: O(n)\n<!-- Add your space complexity here, e.g. $$O(n)$$ -->\n\n# Code\n```\nclass Solution {\n    public String minRemoveToMakeValid(String s) {\n        HashSet<Integer> badIndex = new HashSet<>();\n        ArrayDeque<Integer> st = new ArrayDeque<>();\n\n        for (int i = 0; i < s.length(); i++) {\n            if (s.charAt(i) == \'(\') {\n                st.push(i);\n            } else if (s.charAt(i) == \')\') {\n                if (st.isEmpty()) {\n                    badIndex.add(i);\n                } else {\n                    st.pop();\n                }\n            }\n        }\n\n        while (!st.isEmpty()) {\n            badIndex.add(st.pop());\n        }\n\n        StringBuilder ans = new StringBuilder();\n        for (int i = 0; i < s.length(); i++) {\n            if (!badIndex.contains(i)) {\n                ans.append(s.charAt(i));\n            }\n        }\n        \n        return ans.toString();\n    }\n}\n\n```\n\n# Approach 2\n<!-- Describe your approach to solving the problem. -->\n\n# Complexity\n- Time complexity: O(n)\n<!-- Add your time complexity here, e.g. $$O(n)$$ -->\n\n- Space complexity: O(n)\n<!-- Add your space complexity here, e.g. $$O(n)$$ -->\n\n```\nclass Solution {\n    public String minRemoveToMakeValid(String s) {\n        HashSet<Integer> badIndex = new HashSet<>();\n        int diff = 0;\n\n        for (int i = 0; i < s.length(); i++) {\n            if (s.charAt(i) == \'(\') {\n                diff++;\n            } else if (s.charAt(i) == \')\') {\n                if (diff == 0) {\n                    badIndex.add(i);\n                } else {\n                    diff--;\n                }\n            }\n        }\n\n        for (int i = s.length() - 1; i >= 0 && diff > 0; i--) {\n            if (s.charAt(i) == \'(\') {\n                diff--;\n                badIndex.add(i);\n            }\n        }\n\n        StringBuilder ans = new StringBuilder();\n        for (int i = 0; i < s.length(); i++) {\n            if (!badIndex.contains(i)) {\n                ans.append(s.charAt(i));\n            }\n        }\n        \n        return ans.toString();\n    }\n}\n```\n# Approach 3\n<!-- Describe your approach to solving the problem. -->\n\n# Complexity\n- Time complexity: O(n)\n<!-- Add your time complexity here, e.g. $$O(n)$$ -->\n\n- Space complexity: O(n)\n<!-- Add your space complexity here, e.g. $$O(n)$$ -->\n\n```\nclass Solution {\n    public String removeWhYouCan(String s, char open, char close) {\n        StringBuilder ans = new StringBuilder();\n        int diff = 0;\n\n        for (int i = 0; i < s.length(); i++) {\n            char c = s.charAt(i);\n            if (c == open) {\n                diff++;\n                ans.append(c);\n            } else if (c == close) {\n                if (diff == 0) {\n                    continue;\n                }\n                diff--;\n                ans.append(c);\n            } else {\n                ans.append(c);\n            }\n        }\n\n        return ans.toString();\n    }\n\n    public String minRemoveToMakeValid(String s) {\n        String ans = removeWhYouCan(s, \'(\', \')\');\n        ans = new StringBuilder(ans).reverse().toString();\n        ans = removeWhYouCan(ans, \')\', \'(\');\n        return new StringBuilder(ans).reverse().toString();\n    }\n}\n```\n\n# Approach 4\n<!-- Describe your approach to solving the problem. -->\n\n# Complexity\n- Time complexity: O(n)\n<!-- Add your time complexity here, e.g. $$O(n)$$ -->\n\n- Space complexity: O(n)\n<!-- Add your space complexity here, e.g. $$O(n)$$ -->\n\n```\nclass Solution {\n    public String minRemoveToMakeValid(String s) {\n        StringBuilder ans = new StringBuilder();\n        int diff = 0;\n        int countOpen = 0;\n\n        // First pass to remove invalid closing parentheses and count open parentheses\n        for (int i = 0; i < s.length(); i++) {\n            char c = s.charAt(i);\n            if (c == \'(\') {\n                diff++;\n                countOpen++;\n                ans.append(c);\n            } else if (c == \')\') {\n                if (diff == 0) {\n                    continue;\n                }\n                diff--;\n                ans.append(c);\n            } else {\n                ans.append(c);\n            }\n        }\n\n        // Second pass to remove extra open parentheses\n        StringBuilder res = new StringBuilder();\n        int times = countOpen - diff;\n        for (int i = 0; i < ans.length(); i++) {\n            char c = ans.charAt(i);\n            if (c == \'(\') {\n                times--;\n                if (times < 0) {\n                    continue;\n                }\n            }\n            res.append(c);\n        }\n        \n        return res.toString();\n    }\n}\n```\n
['Java']