1021. Remove Outermost Parentheses
Model: qwen2.5-coder:14b
Topics: Stack
FAANG asked: 1
Acceptance rate: 79.2%
Problem Breakdown
The problem requires us to remove the outermost parentheses from every primitive valid parentheses string in a given valid parentheses string S. A primitive valid parentheses string cannot be split into two nonempty valid parentheses strings. The input is a valid parentheses string S, and the output should be the same string with the outermost parentheses of each primitive component removed.
Inputs:
- A valid parentheses string
S(e.g.,"(()())(())").
Outputs:
- A string with the outermost parentheses of each primitive component removed (e.g.,
"()()()").
Implicit Constraints or Tricky Edge Cases:
- The input string is guaranteed to be a valid parentheses string.
- The input string can be empty, which should return an empty string.
- The input string can have multiple primitive components.
Intuition
A brute-force approach would involve iterating through the string and checking for balanced parentheses, but this could be inefficient in terms of time complexity. A better approach involves using a stack to keep track of open parentheses. By pushing indices of open parentheses onto the stack and popping them when encountering closing parentheses, we can identify primitive components and remove their outermost parentheses.
The key insight is that a primitive component starts with an open parenthesis and ends with a matching close parenthesis, where the stack becomes empty after processing the entire primitive component.
Approach
- Initialize an empty stack to keep track of indices of open parentheses.
- Iterate through the string
S:- If the current character is
'(', push its index onto the stack. - If the current character is
')', pop the top index from the stack. - If the stack becomes empty after popping, it means we have found a primitive component. Remove the outermost parentheses by excluding the characters at the indices of the first and last open/close parentheses in this component.
- If the current character is
- Append the modified primitive components to the result string.
- Return the final result string.
Complexity Analysis
- Time Complexity: O(n), where n is the length of the input string
S. We iterate through the string once, performing constant-time operations for each character. - Space Complexity: O(n) in the worst case, where all characters are open parentheses. The stack can grow up to the size of the input string.
Solution
def removeOuterParentheses(S: str) -> str:
stack = []
result = []
for i, char in enumerate(S):
if char == '(':
stack.append(i)
else:
start_index = stack.pop()
# If stack is empty, we have a complete primitive component
if not stack:
# Append the inner part of the primitive component to the result
result.extend(S[start_index + 1:i])
return ''.join(result)
# Example usage:
print(removeOuterParentheses("(()())(())")) # Output: "()()()"
print(removeOuterParentheses("(()())(())(()(()))")) # Output: "()()()()(())"
print(removeOuterParentheses("()()")) # Output: ""
Edge Cases Handled
- Empty Input: If the input string is empty, the function returns an empty string.
- Single Primitive Component: If the input string consists of a single primitive component, the outermost parentheses are removed correctly.
- Multiple Primitive Components: The function handles strings with multiple primitive components by removing the outermost parentheses of each independently.