Beats 90%🔥||Easy Stack ✅and Naive ✅ with explanation😊😊..
The short form of the question is to print the paranthesis only if it is possible to form a pair..\n\nif a paranthesis is ( then we would have to iterate throug
**The short form of the question is to print the paranthesis only if it is possible to form a pair..**\n\n**if a paranthesis is ```(``` then we would have to iterate throughout the array till we found ```)``` but it is not the optimal one.**\n\n**Approach 1:\nwhy cant we just iterate the array and take the ```min of open and close``` parnthesis, thus only ```min(open,close) pairs``` is possible.**\n**we can just define the ```)``` only when open ```(``` is used and the count is greater than  zero.**\n\n**similarly we can only use the ```(``` only when count>0**\n\n**thus it would take O(n) time..**\n\n\n# Code\n``` Java []\nclass Solution {\n    public String minRemoveToMakeValid(String s) {\n        int open=0,close=0,flag=0;\n        for(int i=0;i<s.length();i++){\n            if(s.charAt(i)==\'(\') {\n                open++;\n                flag+=1;\n            }\n            else if(s.charAt(i)==\')\'&&flag>0) {\n                close++;\n                flag--;\n            }\n        }\n        int k=Math.min(open,close);\n        String ans="";\n        open=k;\n        close=k;\n        for(int i=0;i<s.length();i++){\n            if(s.charAt(i)==\'(\'){\n                if(open>0) {\n                    ans+=\'(\';\n                    open--;\n                }\n                continue;\n            } \n            if(s.charAt(i)==\')\') {\n               if(close>0&&close>open) {\n                  ans+=\')\'; \n                  close--;\n               }\n               continue;\n            }\n            else ans+=s.charAt(i);\n        }\n        return ans;\n    }\n}\n```\n\n``` Python3 []\nclass Solution:\n    def minRemoveToMakeValid(self, s: str) -> str:\n        open_count = 0\n        close_count = 0\n        flag = 0\n        ans = ""\n        \n        for char in s:\n            if char == \'(\':\n                open_count += 1\n                flag += 1\n            elif char == \')\' and flag > 0:\n                close_count += 1\n                flag -= 1\n        \n        k = min(open_count, close_count)\n        open_count = k\n        close_count = k\n        \n        for char in s:\n            if char == \'(\':\n                if open_count > 0:\n                    ans += \'(\'\n                    open_count -= 1\n                continue\n            if char == \')\':\n                if close_count > 0 and close_count > open_count:\n                    ans += \')\'\n                    close_count -= 1\n                continue\n            else:\n                ans += char\n        \n        return ans\n\n```\n\n``` C++ []\n#include <string>\n#include <algorithm>\n\nclass Solution {\npublic:\n    std::string minRemoveToMakeValid(std::string s) {\n        int open = 0, close = 0, flag = 0;\n        for (char c : s) {\n            if (c == \'(\') {\n                open++;\n                flag++;\n            } else if (c == \')\' && flag > 0) {\n                close++;\n                flag--;\n            }\n        }\n        \n        int k = std::min(open, close);\n        std::string ans = "";\n        open = k;\n        close = k;\n        for (char c : s) {\n            if (c == \'(\') {\n                if (open > 0) {\n                    ans += \'(\';\n                    open--;\n                }\n                continue;\n            }\n            if (c == \')\') {\n                if (close > 0 && close > open) {\n                    ans += \')\';\n                    close--;\n                }\n                continue;\n            } else {\n                ans += c;\n            }\n        }\n        return ans;\n    }\n};\n\n```\n``` JavaScript []\n/**\n * @param {string} s\n * @return {string}\n */\nvar minRemoveToMakeValid = function(s) {\n    \n\n\n\n        let open = 0, close = 0, flag = 0;\n        for (let i = 0; i < s.length; i++) {\n            if (s[i] === \'(\') {\n                open++;\n                flag++;\n            } else if (s[i] === \')\' && flag > 0) {\n                close++;\n                flag--;\n            }\n        }\n        \n        let k = Math.min(open, close);\n        let ans = \'\';\n        open = k;\n        close = k;\n        for (let i = 0; i < s.length; i++) {\n            if (s[i] === \'(\') {\n                if (open > 0) {\n                    ans += \'(\';\n                    open--;\n                }\n                continue;\n            }\n            if (s[i] === \')\') {\n                if (close > 0 && close > open) {\n                    ans += \')\';\n                    close--;\n                }\n                continue;\n            } else {\n                ans += s[i];\n            }\n        }\n        return ans;\n}\n\n\n```\n\n\n**Approach 2:\nYeah we can just use stack to peep() whether there is any trailing \n```(``` before addng ```)``` so that we can just pop() that thing out of it**\n\n\n**so basically youre going to add the indexes on the stack whenever you realize a ```close )``` does not have any ```open(``` ,if there is a pair availbale just pop() the pair.This can be done,whenever you see a close with trailing open just pop() open and move further**\n\n**then just append the whole string except the indexes which are present inside the stack they are the indexes which do not form a pair**\n\n``` Java []\nclass Solution {\n    public String minRemoveToMakeValid(String s) {\n        Stack <Integer> st=new Stack<>();\n        for(int i=0;i<s.length();i++){\n            if(s.charAt(i)==\'(\') st.push(i);\n            else if(s.charAt(i)==\')\'){\n                if(!st.isEmpty()&&s.charAt((int)st.peek())==\'(\'){\n                    st.pop();\n                }\n                else st.push(i);\n            }\n            else continue;\n        }\n        StringBuilder sb=new StringBuilder();\n        for(int i=s.length()-1;i>=0;i--){\n            if(!st.isEmpty()&&(int)st.peek()==i) {\n                st.pop();\n                continue;\n            }\n            else sb.append(s.charAt(i));\n        }\n        return sb.reverse().toString();\n    }\n}\n```\n```Python3 []\nclass Solution:\n    def minRemoveToMakeValid(self, s: str) -> str:\n        stack = []\n        for i, char in enumerate(s):\n            if char == \'(\':\n                stack.append(i)\n            elif char == \')\':\n                if stack and s[stack[-1]] == \'(\':\n                    stack.pop()\n                else:\n                    stack.append(i)\n        \n        result = []\n        for i, char in enumerate(s):\n            if stack and i == stack[0]:\n                stack.pop(0)\n                continue\n            result.append(char)\n        \n        return \'\'.join(result)\n\n```\n\n```JavaScript []\nclass Solution {\n    minRemoveToMakeValid(s) {\n        const stack = [];\n        for (let i = 0; i < s.length; i++) {\n            if (s[i] === \'(\') {\n                stack.push(i);\n            } else if (s[i] === \')\') {\n                if (stack.length && s[stack[stack.length - 1]] === \'(\') {\n                    stack.pop();\n                } else {\n                    stack.push(i);\n                }\n            }\n        }\n        \n        let result = \'\';\n        for (let i = 0; i < s.length; i++) {\n            if (stack.length && i === stack[0]) {\n                stack.shift();\n                continue;\n            }\n            result += s[i];\n        }\n        \n        return result;\n    }\n}\n```\n\n
['String', 'Stack', 'C++', 'Java', 'Python3', 'JavaScript']