We use cookies (including Google cookies) to personalize ads and analyze traffic. By continuing to use our site, you accept our Privacy Policy.

SimplyLeet
TagsCompaniesDisclaimersPrivacyTermsContactAbout Us

Remove Outermost Parentheses

Number: 1078

Difficulty: Easy

Paid? No

Companies: Amazon, Bloomberg, Microsoft, Adobe, Apple, Meta, Google

Problem Description

Given a valid parentheses string s, the goal is to remove the outermost parentheses of every primitive valid parentheses substring. A primitive parentheses string is nonempty and cannot be split into two nonempty valid parentheses substrings.

Key Insights

  • Use a counter to track the current nesting depth for the parentheses.
  • Increment the counter when encountering an opening parenthesis '('.
  • Decrement the counter when encountering a closing parenthesis ')'.
  • Append characters to the result only when they are not the outermost parentheses (i.e., when the counter is not transitioning from 0 to 1 or from 1 back to 0).
  • This approach avoids the need for an explicit stack data structure by simply tracking depth.

Space and Time Complexity

Time Complexity: O(n) because we process each character once.
Space Complexity: O(n) for storing the result, in the worst-case scenario.

Solution

Iterate through the input string and maintain a depth counter that reflects the current nesting level of parentheses. For every opening parenthesis, if the depth is greater than zero, add it to the result, then increase the depth. For every closing parenthesis, decrease the depth first, then add it to the result if the current depth remains above zero. This effectively removes the outermost parentheses from each primitive substring.

Code Solutions

# Python solution for Remove Outermost Parentheses problem.
def removeOuterParentheses(s: str) -> str:
    result = []  # List to accumulate result characters.
    depth = 0   # Counter to track current parentheses depth.
    # Iterate over each character in the string.
    for char in s:
        if char == '(':
            # If depth is greater than 0, then it's not an outer parenthesis.
            if depth > 0:
                result.append(char)
            depth += 1  # Increase the depth.
        else:
            depth -= 1  # Decrease the depth.
            # If depth is still above 0, then it's not an outer parenthesis.
            if depth > 0:
                result.append(char)
    return "".join(result)

# Test cases:
print(removeOuterParentheses("(()())(())"))         # Expected output: "()()()"
print(removeOuterParentheses("(()())(())(()(()))"))   # Expected output: "()()()()(())"
print(removeOuterParentheses("()()"))                # Expected output: ""
← Back to All Questions