Track nesting depth, appending an opening parenthesis only after entering a primitive and a closing one only before leaving it.
Complexity
O(n) time and O(n) output space.
Remove the first and last parenthesis from every primitive part of a valid parentheses string.
Track nesting depth, appending an opening parenthesis only after entering a primitive and a closing one only before leaving it.
O(n) time and O(n) output space.
package main
func removeOuterParentheses(s string) string {
result := make([]byte, 0, len(s))
depth := 0
for index := range s {
if s[index] == '(' {
if depth > 0 {
result = append(result, s[index])
}
depth++
} else {
depth--
if depth > 0 {
result = append(result, s[index])
}
}
}
return string(result)
}
class Solution:
def removeOuterParentheses(self, s: str) -> str:
result: list[str] = []; depth = 0
for character in s:
if character == "(":
if depth: result.append(character)
depth += 1
else:
depth -= 1
if depth: result.append(character)
return "".join(result)
function removeOuterParentheses(s: string): string {
const result: string[] = []; let depth = 0;
for (const character of s) { if (character === "(") { if (depth > 0) result.push(character); depth += 1; } else { depth -= 1; if (depth > 0) result.push(character); } }
return result.join("");
}