Let's Form Couples ❤️‍🔥 Part - II | Very Easy Explanation + Full Concept + illustrations
Youtube Explanation\nSoon to be on Channel : https://www.youtube.com/@Intuit_and_Code\nEdited:\nhttps://youtu.be/ZRr2UiHIBBA?si=kUm0zzURb2UkN91H\n\n> I would re
# Youtube Explanation\nSoon to be on Channel : https://www.youtube.com/@Intuit_and_Code\nEdited:\nhttps://youtu.be/ZRr2UiHIBBA?si=kUm0zzURb2UkN91H\n\n> I would recommend to read this article first : **[Link](https://leetcode.com/problems/minimum-number-of-swaps-to-make-the-string-balanced/solutions/5886919/let-s-form-couples-very-easy-illustration-full-concept)**\nI Covered Nearly Same Concept as in that article, Let\'s Understand them again\n\n# Intuition & Approach\n    \n![image.png](https://assets.leetcode.com/users/images/0339f770-744d-4ccd-83ba-6a59a93bf406_1728458776.2959945.png)\n![image.png](https://assets.leetcode.com/users/images/bb678815-a018-4a96-8f45-fe941fb0b908_1728458783.9091568.png)\n![image.png](https://assets.leetcode.com/users/images/dcce6149-3005-498c-9859-bf0986e545d9_1728464144.7335155.png)\n\n> If Ya already read yesterday\'s article, then below feels similar\n\n![image.png](https://assets.leetcode.com/users/images/1f568db1-4824-4c8c-a8a4-45879a49dea7_1728458808.2218482.png)\n![image.png](https://assets.leetcode.com/users/images/773f41b6-b2a4-4caa-8a8b-a412051ac955_1728458817.962986.png)\n![image.png](https://assets.leetcode.com/users/images/fffbd0cd-c04b-4c17-b681-a47fa45650fd_1728458830.6601665.png)\n\n# Code\n```c++ [ ]\nclass Solution {\npublic:\n    int minAddToMakeValid(string s) {\n        stack<char> st;\n\n        for (auto& val : s) { // for(int i=0;i<s.size();i++)\n            if (st.empty()) {\n                st.push(val); // val = s[i]\n            } \n            else if (st.top() == \'(\' and val == \')\') {\n                st.pop();\n            } \n            else {\n                st.push(val); // val = s[i]\n            }\n        }\n\n        return st.size();\n    }\n};\n```\n``` java [ ]\nclass Solution {\n    public int minAddToMakeValid(String s) {\n        Stack<Character> st = new Stack<>();\n\n        for (char val : s.toCharArray()) {\n            if (st.isEmpty()) {\n                st.push(val);\n            } \n            else if (st.peek() == \'(\' && val == \')\') {\n                st.pop();\n            } \n            else {\n                st.push(val);\n            }\n        }\n\n        return st.size();\n    }\n}\n```\n``` python [ ]\nclass Solution:\n    def minAddToMakeValid(self, s: str) -> int:\n        stack = []\n\n        for val in s:\n            if not stack:\n                stack.append(val)\n            elif stack[-1] == \'(\' and val == \')\':\n                stack.pop()\n            else:\n                stack.append(val)\n\n        return len(stack)\n```\n\n![image.png](https://assets.leetcode.com/users/images/0b1127c2-a925-4a28-8f7b-419223393129_1728459450.2751002.png)\n![image.png](https://assets.leetcode.com/users/images/1d47d850-3c0d-42ce-aec2-2180b71960c2_1728458850.3163996.png)\n\n\n# Complexity [ Optimized ]\n- Time complexity: O(n)\n<!-- Add your time complexity here, e.g. $$O(n)$$ -->\n\n- Space complexity: O(1)\n<!-- Add your space complexity here, e.g. $$O(n)$$ -->\n\n# Code\n```c++ []\nclass Solution {\npublic:\n    int minAddToMakeValid(string s) {\n        int girl=0, boys=0;\n\n        for(int i=0;i<s.size();i++){\n            if(boys>0 and s[i]==\')\'){\n                // couple formed\n                // no need to increase girl count\n                // eventually boy decreased\n                boys--;\n            }\n            else{\n                if(s[i]==\'(\'){boys++;}\n                else{girl++;}\n            }\n        }\n\n        return girl+boys;\n    }\n};\n```\n``` java [ ]\nclass Solution {\n    public int minAddToMakeValid(String s) {\n        int girl = 0, boys = 0;\n\n        for (int i = 0; i < s.length(); i++) {\n            if (boys > 0 && s.charAt(i) == \')\') {\n                // Couple formed, decrease boys count\n                boys--;\n            } \n            else {\n                if (s.charAt(i) == \'(\') {\n                    boys++;\n                } \n                else {\n                    girl++;\n                }\n            }\n        }\n\n        return girl + boys;\n    }\n}\n```\n``` python [ ]\nclass Solution:\n    def minAddToMakeValid(self, s: str) -> int:\n        girl, boys = 0, 0\n\n        for i in range(len(s)):\n            if boys > 0 and s[i] == \')\':\n                # Couple formed, decrease boys count\n                boys -= 1\n            else:\n                if s[i] == \'(\':\n                    boys += 1\n                else:\n                    girl += 1\n\n        return girl + boys\n```
['Math', 'String', 'Stack', 'Greedy', 'String Matching', 'Python', 'C++', 'Java', 'Python3']