Java solution 5 lines, faster and less memory than 99% (example also in C++, Python)
Although this problem is labeled as \'easy\' it can seem quite difficult at first, especially due to the way the writeup was written.\n\nHere is an advice, whic
Although this problem is labeled as \'easy\' it can seem quite difficult at first, especially due to the way the writeup was written.\n\nHere is an advice, which has always helped me break down parenthesis problems. There is something called Catalan structures or Catalan numbers. Now, bear with me! This might seem awfully complicated since Catalan numbers is something abstract and mathematical. But take a look at table 2 on page 2 in this paper:\n http://www.geometer.org/mathcircles/catalan.pdf\n\nSee these \'Mountain Ranges\'? These can be thought of as matches. Where you would add an upwards leaning match for an open parenthesis and a downwards leaning match for a closing parenthesis. Here is the important part: A Mountain range like this, where we start at the bottom and end at the bottom is a valid parenthesis.\n\nNow, if you draw on a piece of paper the three examples given in the write-up. You can see that the problem is only asking you to remove the lowest level of each \'mountain\'. Since that is the case, the only thing we need is a counter while we iterate through the characters forming the parenthesis string. For each level we go up (open parenthesis) we increment the counter while we decrement it while we go down. So you can think of the counter as keeping track of the elevation in the mountain range.\n\nNow, what I did in my solution was to initialize a counter and a string builder. Whenever there was an open parenthesis at levels other than zero I added the char to the string builder. Whenever there was a closing parenthesis at a level other than 1, I added the parenthesis to the string builder. This effectively removes the bottom level for each mountain in the mountain range\n\nWhy does this work? Try drawing it out!\n\n**Java**\n```\nclass Solution {\n    public String removeOuterParentheses(String s) {\n        StringBuilder sb = new StringBuilder();\n        int count = 0;\n        for(char c : s.toCharArray())\n            if      (c == \'(\' && count++ != 0) sb.append(c);\n            else if (c == \')\' && count-- != 1) sb.append(c);\n        return sb.toString();\n    }\n}\n```\n\n**c++**\n```\nclass Solution {\npublic:\n    string removeOuterParentheses(string s) \n        \n        int count = 0;            // count elevation\n        char output[s.length()];  // the output string\n        int head = 0;             // write head of buffer\n        \n        for(int i = 0; i < s.length(); i++){\n            char c = s[i];\n            if      (c == \'(\' && count++ > 0) output[head++] = c;\n            else if (c == \')\' && count-- > 1) output[head++] = c;\n        }\n        \n        // null terminate the string and return\n        output[head] = 0;\n        return output;\n    }\n};\n```\n\n**Python 3**\nNote that using an array, keeps the running time linear (amortized) appending strings would result in O(N^2)\n```\nclass Solution:\n    def removeOuterParentheses(self, s: str) -> str:\n        output = []\n        count = 0\n        for c in s:\n            if c == \'(\':\n                if count > 0: output.append(c)\n                count += 1\n            if c == \')\':\n                if count > 1: output.append(c)\n                count -= 1\n        return "".join(output)\n```
[]