Removing Outer Layers of Parentheses in Linear Time || 4ms Runtime
Intuition\n Describe your first thoughts on how to solve this problem. \nThe problem is about removing the outermost parentheses from a valid string of parenthe
# Intuition\n<!-- Describe your first thoughts on how to solve this problem. -->\nThe problem is about removing the outermost parentheses from a valid string of parentheses. The idea is that for each balanced section of the string (or primitive), you want to remove the first opening parenthesis ( and the last closing parenthesis ).\n\n# Approach\n<!-- Describe your approach to solving the problem. -->\n1. Tracking the Balance: We maintain a counter count to keep track of the balance between the opening ( and closing ) parentheses. This helps us identify when we are inside a balanced group of parentheses.\n\n2. Iterate Through the String: We iterate through each character in the string s:\n\n- If the character is an opening parenthesis (:\n   - If count is not zero, it means we are inside a balanced group   (not at the outermost level), so we add this ( to our answer string ans.\n   - Increment the count since we encountered an opening parenthesis.\n- If the character is a closing parenthesis ):\n   - Decrement the count first. If the count is still greater than zero after decrementing, it means we are inside a balanced group, so we add this ) to ans.\n\n3. Building the Result: The result string ans accumulates all the characters that are not part of the outermost parentheses.\n\n4. Return the Result: After iterating through the entire string, we return the string ans which contains the input string s with the outermost parentheses removed.\n\n# Complexity\n- Time complexity: O(N)\n<!-- Add your time complexity here, e.g. $$O(n)$$ -->\nThe time complexity is O(n), where n is the length of the string s. We iterate through the string once, making this approach linear in time.\n\n- Space complexity: O(N)\n<!-- Add your space complexity here, e.g. $$O(n)$$ -->\nSpace Complexity: The space complexity is O(n), as we are creating a new string ans to store the result. In the worst case, this string could be nearly as long as the input string s.\n\n# Code\n```cpp []\nclass Solution {\npublic:\n    string removeOuterParentheses(string s) {\n        int count = 0;\n        string ans = "";\n        int i = 0, n = s.size();\n\n        while(i < n) {\n            if(s[i] == \'(\') {\n                if(count != 0) {\n                    ans += s[i];\n                }\n                count++; \n            } else if (s[i] == \')\') {\n                if(count > 1) {\n                    ans += s[i];\n                }\n                    count--; \n            }\n\n            i++;\n        }\n        return ans;\n    }\n};\n```\n```java []\nclass Solution {\n    public String removeOuterParentheses(String s) {\n        int count = 0;\n        StringBuilder ans = new StringBuilder();\n\n        for (char c : s.toCharArray()) {\n            if (c == \'(\') {\n                if (count != 0) {\n                    ans.append(c);\n                }\n                count++;\n            } else {\n                if (count > 1) {\n                    ans.append(c);\n                }\n                count--;\n            }\n        }\n\n        return ans.toString();\n    }\n}\n\n```\n```javascript []\nvar removeOuterParentheses = function(s) {\n    let count = 0;\n    let ans = \'\';\n\n    for (let c of s) {\n        if (c === \'(\') {\n            if (count !== 0) {\n                ans += c;\n            }\n            count++;\n        } else {\n            if (count > 1) {\n                ans += c;\n            }\n            count--;\n        }\n    }\n\n    return ans;\n};\n\n```\n```python []\nclass Solution:\n    def removeOuterParentheses(self, s: str) -> str:\n        count = 0\n        ans = []\n\n        for c in s:\n            if c == \'(\':\n                if count != 0:\n                    ans.append(c)\n                count += 1\n            else:\n                if count > 1:\n                    ans.append(c)\n                count -= 1\n\n        return \'\'.join(ans)\n\n```\n\n
['String', 'Python', 'C++', 'Java', 'JavaScript']