C++ , JAVA : SIMPLEAND EASY Approach: Using a Stack to Make Parentheses Valid 🥞
Intuition \uD83D\uDCA1\nImagine you\'re at a party \uD83C\uDF89 where everyone is wearing either a left or right shoe \uD83D\uDC5E\uD83D\uDC60. Our goal is to m
# Intuition \uD83D\uDCA1\nImagine you\'re at a party \uD83C\uDF89 where everyone is wearing either a left or right shoe \uD83D\uDC5E\uD83D\uDC60. Our goal is to make sure every left shoe \uD83D\uDC5E has a matching right shoe \uD83D\uDC60. But oh no! Some shoes are unmatched! \uD83D\uDE31\n\nOur job is to count how many lonely shoes are left and how many new shoes \uD83D\uDC5E\uD83D\uDC60 we need to bring in to pair everyone up. In this case, the shoes are parentheses, and we need to make sure every ( has a matching )!\n\n\n\n<!-- Describe your first thoughts on how to solve this problem. -->\n\n# Approach \uD83D\uDEE0\uFE0F\n\n<!-- Describe your approach to solving the problem. -->\n1. We\u2019ll use a stack \uD83E\uDD5E (our magical shoe-closet \uD83E\uDDF3) to keep track of unmatched parentheses:\n- If we see a left parenthesis (, we\u2019ll throw it into the stack \uD83E\uDD5E (like tossing shoes into the closet \uD83E\uDDF3).\n- If we see a right parenthesis ), we\u2019ll check if there\u2019s already a left parenthesis ( waiting for it in the closet:\n- If yes \u2705, we match them and toss the pair away! \uD83D\uDC5E\uD83D\uDC60\n- If no \u274C, we\u2019ll toss the right parenthesis ) into the stack \uD83E\uDD5E as a sad lonely shoe! \uD83D\uDE22\n2. By the end, all that\u2019s left in the stack \uD83E\uDD5E are the lonely unmatched parentheses \uD83D\uDE14. The size of the stack tells us how many new shoes \uD83D\uDC5E\uD83D\uDC60 (parentheses) we need to bring to make things even!\n\n# Complexity \uD83D\uDE80\n\n- Time complexity:\n\nWe only go through the string once \uD83D\uDC40, checking each character and either pushing or popping from the stack \uD83E\uDD5E. So, the time complexity is O(n), where n is the length of the string. \u26A1\n\n- Space complexity:\n\nThe stack can store up to n parentheses \uD83E\uDD5E in the worst case (when every parenthesis is unmatched \uD83D\uDE31), so the space complexity is O(n). \uD83D\uDCE6\n![48b755ae-c41b-474d-966e-aa5674e41ff4_1720943081.9620614.jpeg](https://assets.leetcode.com/users/images/87956ec4-2c78-4493-952f-c9f7e9b24144_1728495951.9930718.jpeg)\n\n# Code \uD83D\uDC69\u200D\uD83D\uDCBB\uD83D\uDC68\u200D\uD83D\uDCBB\n\n```cpp []\nclass Solution {\npublic:\n    int minAddToMakeValid(string s) {\n\n        stack<int>st;\n        for(int i=0;i<s.size();i++){\n            if(!st.empty() && st.top()==\'(\'){\n                if(s[i]==\')\'){\n                    st.pop();\n                }else{\n                    st.push(s[i]);\n                }\n            }else{\n                 st.push(s[i]);\n            }\n        }\n\n        if(st.size()==0){\n            return 0;\n        }else{\n            return st.size();\n        }\n    }\n};\n```
['String', 'Stack', 'C++', 'Java']