3 Interview Approaches with Video Explanation 🔥 ||(Stack+Visited)->(Only Stack)->(No Stack) ✅
Intuition\n Describe your first thoughts on how to solve this problem. \nParentheses (think about stacks). \nIn Interviews you need to follow this pattern. Firs
# Intuition\n<!-- Describe your first thoughts on how to solve this problem. -->\n**Parentheses (think about stacks). \nIn Interviews you need to follow this pattern. First you need to explain Brute Force and you can optimize in the subsequent approaches.**\n\n\n# ***Easy Video Explanation***\n\n***Most of you knows the solution but approaches are important.\n(This video helps you, how to approach this types of problems in interviews)***\n\nhttps://youtu.be/mIypvv75WJ4\n    \n\n# Code (Stack + Visited)\n\n\n```C++ []\nclass Solution {\npublic:\n    string minRemoveToMakeValid(string s) {\n        int n=s.size();\n        vector<bool>vis(n,1);\n        stack<int>st;\n        for(int i=0;i<n;i++) {\n            if(s[i]>=\'a\' && s[i]<=\'z\')\n                continue;\n            if(s[i]==\'(\') {\n                st.push(i);\n            } else {\n                if(!st.empty()) {\n                    st.pop();\n                } else {\n                    vis[i]=0;\n                }\n            }\n        }\n        while(!st.empty()) {\n            vis[st.top()]=0;\n            st.pop();\n        }\n        string ans="";\n        for(int i=0;i<n;i++) {\n            if(vis[i]==1)\n                ans.push_back(s[i]);\n        }\n        return ans;\n    }\n};\n```\n```python []\nclass Solution:\n    def minRemoveToMakeValid(self, s: str) -> str:\n        n = len(s)\n        vis = [False] * n\n        st = []\n        for i in range(n):\n            if s[i].islower():\n                continue\n            if s[i] == \'(\':\n                st.append(i)\n            else:\n                if st:\n                    st.pop()\n                else:\n                    vis[i] = True\n        while st:\n            vis[st.pop()] = True\n        ans = ""\n        for i in range(n):\n            if not vis[i]:\n                ans += s[i]\n        return ans\n\n```\n```Java []\nimport java.util.Stack;\n\nclass Solution {\n    public String minRemoveToMakeValid(String s) {\n        int n = s.length();\n        boolean[] vis = new boolean[n];\n        Stack<Integer> st = new Stack<>();\n        for (int i = 0; i < n; i++) {\n            if (Character.isLowerCase(s.charAt(i)))\n                continue;\n            if (s.charAt(i) == \'(\') {\n                st.push(i);\n            } else {\n                if (!st.isEmpty()) {\n                    st.pop();\n                } else {\n                    vis[i] = true;\n                }\n            }\n        }\n        while (!st.isEmpty()) {\n            vis[st.pop()] = true;\n        }\n        StringBuilder ans = new StringBuilder();\n        for (int i = 0; i < n; i++) {\n            if (!vis[i])\n                ans.append(s.charAt(i));\n        }\n        return ans.toString();\n    }\n}\n\n```\n\n# Complexity\n- Time complexity:\n<!-- Add your time complexity here, e.g. $$O(n)$$ -->\n    O(N)\n    \n\n- Space complexity:\n<!-- Add your space complexity here, e.g. $$O(n)$$ -->\n    O(N)\n\n    \n\n# Code (Only Stack)\n\n\n```C++ []\nclass Solution {\npublic:\n    string minRemoveToMakeValid(string s) {\n        int n=s.size();\n        stack<int>st;\n        for(int i=0;i<n;i++) {\n            if(s[i]>=\'a\' && s[i]<=\'z\')\n                continue;\n            if(s[i]==\'(\') {\n                st.push(i);\n            } else {\n                if(!st.empty()) {\n                    st.pop();\n                } else {\n                    s[i]=\'#\';\n                }\n            }\n        }\n        while(!st.empty()) {\n            s[st.top()]=\'#\';\n            st.pop();\n        }\n        string ans="";\n        for(int i=0;i<n;i++) {\n            if(s[i]!=\'#\')\n                ans.push_back(s[i]);\n        }\n        return ans;\n    }\n};\n```\n# Complexity\n- Time complexity:\n<!-- Add your time complexity here, e.g. $$O(n)$$ -->\n    O(N)\n    \n\n- Space complexity:\n<!-- Add your space complexity here, e.g. $$O(n)$$ -->\n    O(N)\n\n\n# Code (No Stack O(1) space)\n\n\n```C++ []\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# Complexity\n- Time complexity:\n<!-- Add your time complexity here, e.g. $$O(n)$$ -->\n    O(N)\n    \n\n- Space complexity:\n<!-- Add your space complexity here, e.g. $$O(n)$$ -->\n    O(1)\n\n# ***If you like the solution Please Upvote and subscribe to my youtube channel***\n***It Motivates me to record more videos***\n\n*Thank you* \uD83D\uDE00
['String', 'Stack', 'Python', 'C++', 'Java']