Ridiculously Simple JAVA O(n) Solution + Explanation [0ms Beats 100% Time & Memory]
Explanation:\nSince the input String only consists of parentheses we don\'t even have to mainatain a Stack. We can simply maintain a counter which is O(1) and k
**Explanation:**\nSince the input String only consists of parentheses we don\'t even have to mainatain a Stack. We can simply maintain a counter which is O(1) and keep incrementing and decrementing it\'s value based on the opening/closing bracket.\n\n**Algorithm:**\n1. Convert the given input String to a `char` array and start scanning.\n2. Maintain a `sum` counter (Initially 0) and for every following character in the input char array,\n3. When, `(` check whether **sum** is greater than **zero** and if yes, add this char to your String Builder; Also, increment the **sum** by **1** \n4. When, `)` decrement the **sum** by **1** and then, check whether **sum** is greater than **zero** and if yes, add this char to your String Builder;\n5. Return the string from your builder.\n\n**Code:**\n```\npublic String removeOuterParentheses(String S) {\n\tStringBuilder builder = new StringBuilder();\n\tchar[] chr = S.toCharArray();\n\tint sum = 0;\n\tfor (int i = 0; i < chr.length; i++) {\n\t\tif (chr[i] == \'(\') {\n\t\t\tif (sum > 0) { builder.append(chr[i]); }\n\t\t\tsum += 1;\n\t\t} else {\n\t\t\tsum -= 1;\n\t\t\tif (sum > 0) { builder.append(chr[i]); }\n\t\t}\n\t}\n\treturn builder.toString();\n}\n```\n\n**Compressed Version:**\n```\npublic String removeOuterParentheses(String S) {\n\tStringBuilder builder = new StringBuilder();\n\tchar[] chr = S.toCharArray();\n\tint sum = 0;\n\tfor (int i = 0; i < chr.length; i++) {\n\t\tif ((chr[i] == \'(\' && sum++ > 0) || (chr[i] == \')\' && --sum > 0)) {\n\t\t\tbuilder.append(chr[i]);\n\t\t}\n\t}\n\treturn builder.toString();\n}\n```
[]