Skip to main content
Talentd

Remove Outermost Parentheses - Solution & Explanation

EasyStringStack14 min readAsked at: Amazon, Microsoft, Meta +3
Practice this problem

Problem Statement

A valid parentheses string is either empty "", "(" + A + ")", or A + B, where A and B are valid parentheses strings, and + represents string concatenation.

  • For example, "", "()", "(())()", and "(()(()))" are all valid parentheses strings.

A valid parentheses string s is primitive if it is nonempty, and there does not exist a way to split it into s = A + B, with A and B nonempty valid parentheses strings.

Given a valid parentheses string s, consider its primitive decomposition: s = P1 + P2 + ... + Pk, where Pi are primitive valid parentheses strings.

Return s after removing the outermost parentheses of every primitive string in the primitive decomposition of s.

 

Example 1:

Input: s = "(()())(())"
Output: "()()()"
Explanation: 
The input string is "(()())(())", with primitive decomposition "(()())" + "(())".
After removing outer parentheses of each part, this is "()()" + "()" = "()()()".

Example 2:

Input: s = "(()())(())(()(()))"
Output: "()()()()(())"
Explanation: 
The input string is "(()())(())(()(()))", with primitive decomposition "(()())" + "(())" + "(()(()))".
After removing outer parentheses of each part, this is "()()" + "()" + "()(())" = "()()()()(())".

Example 3:

Input: s = "()()"
Output: ""
Explanation: 
The input string is "()()", with primitive decomposition "()" + "()".
After removing outer parentheses of each part, this is "" + "" = "".

 

Constraints:

  • 1 <= s.length <= 105
  • s[i] is either '(' or ')'.
  • s is a valid parentheses string.

Approach Overview

Problem Overview: You are given a valid parentheses string s. The string can be split into multiple primitive valid parentheses substrings. The task is to remove the outermost pair of parentheses from every primitive part and return the final combined string.

Approach 1: Using a Counter to Track Depth (O(n) time, O(1) space)

This approach tracks the current nesting depth while iterating through the string once. Increment the depth when encountering '(' and decrement it when encountering ')'. The key insight: characters should only be added to the result when they are not the outermost parentheses. For an opening bracket, append it only if the current depth is already greater than zero before incrementing. For a closing bracket, decrement first and append only if the depth remains greater than zero. This effectively strips the first and last parentheses of each primitive group without explicitly splitting the string. Since the algorithm performs a single pass and only maintains an integer counter, it runs in O(n) time with O(1) extra space. This method is the most common solution when working with string traversal problems involving balanced parentheses.

Approach 2: Stack-Based Iteration (O(n) time, O(n) space)

A more explicit method uses a stack to simulate the structure of nested parentheses. Push an index or character when encountering '(' and pop when encountering ')'. The stack size represents the current nesting level. When processing characters, skip the parentheses that correspond to the outermost layer of each primitive substring. In practice, append characters only when the stack size after the operation indicates you are inside a nested level. While this approach mirrors how many stack-based parsing algorithms work, it uses additional memory proportional to the nesting depth. The runtime remains O(n) because each character is pushed and popped at most once.

Recommended for interviews: The depth counter solution is the expected answer. It shows you recognize that the stack structure is unnecessary because the nesting level alone determines whether a parenthesis is outermost. The stack approach demonstrates understanding of stack-driven parsing, but the counter approach is cleaner, uses constant space, and signals strong problem-solving instincts.

Approach 1: Approach 1: Using a Counter to Track Depth

This approach uses a counter to track the depth of the current parentheses level. As you iterate through the string, increment the count whenever you see '(', and decrement it on ')'. The outermost parentheses of a primitive section occur whenever the depth transitions from 0 to 1 (for '(') or from 1 to 0 (for ')'). These should be skipped in your final result.

This C implementation iterates over the input string and uses a simple integer counter to track the depth of parenthesis nesting. When a '(' is found and the level before incrementing was greater than 0, it is part of the inner primitive string. Likewise, if before decrementing on ')' the level was greater than 1, it is part of the inner primitive. This effectively ignores the outermost parentheses.

Code

CC++JavaPythonC#JavaScript

C

C++

Java

Python

C#

JavaScript

Complexity

Time Complexity: O(n), where n is the length of the string, because it processes each character exactly once.
Space Complexity: O(n), due to the storage of the output string.

Try this approach in the editor →

Approach 2: Approach 2: Stack-Based Iteration

This approach leverages a stack-like mechanism to mimic the actual stack process of valid parentheses. Instead of using a stack data structure, it simply uses a counter to determine valid scope levels, mimicking pushing and popping operations.

This implementation strategy using just an integer counter, simulates pushing '(' onto a 'stack' by incrementing, and popping ')' by decrementing. The openCount only allows append operations within the valid range, thus removing the outermost parentheses effectively.

Code

CC++JavaPythonC#JavaScript

C

C++

Java

Python

C#

JavaScript

Complexity

Time Complexity: O(n), with n being the string length as it requires one linear pass.
Space Complexity: O(n) used for the result string.

Try this approach in the editor →

Approach 3: Default Approach

Code

PythonJavaC++GoTypeScriptRust

Python

Java

C++

Go

TypeScript

Rust

Try this approach in the editor →

Complexity Comparison

ApproachComplexity
Approach 1: Using a Counter to Track Depth

Time Complexity: O(n), where n is the length of the string, because it processes each character exactly once.
Space Complexity: O(n), due to the storage of the output string.

Approach 2: Stack-Based Iteration

Time Complexity: O(n), with n being the string length as it requires one linear pass.
Space Complexity: O(n) used for the result string.

Default Approach—

Detailed Complexity Analysis

ApproachTimeSpaceWhen to Use
Counter to Track DepthO(n)O(1)Best choice for interviews and production code when only nesting depth matters
Stack-Based IterationO(n)O(n)Useful when explicitly modeling nested structure or extending to complex parsing problems

Video Solution

1021. Remove Outermost Parentheses | Leetcode | Easy Problem | Strings | Stacks | Counter Approach • FastForward Coders - by Gurmeet • 63,447 views views

Watch 9 more video solutions →

Frequently Asked Questions

Is Remove Outermost Parentheses easy or hard?
Remove Outermost Parentheses is classified as an Easy problem on LeetCode with a high acceptance rate. The main challenge is recognizing that tracking nesting depth is enough to identify and remove the outermost parentheses from each primitive substring.
Remove Outermost Parentheses Python/Java solution
In Python or Java, iterate through the string while tracking depth. Append characters only when the current nesting level is not the outermost. The implementation typically uses a string builder or list for efficient concatenation and completes in O(n) time.
How to solve Remove Outermost Parentheses in O(n)?
Iterate through the string while maintaining a nesting depth counter. When encountering '(', append it only if the current depth is already greater than zero, then increment the depth. When encountering ')', decrement the depth first and append it only if the new depth remains greater than zero. This removes the outermost layer from each primitive substring.
What is the best approach for Remove Outermost Parentheses?
The best approach uses a depth counter while scanning the string once. Increase the depth for '(' and decrease it for ')', but only append characters when the depth indicates they are not part of the outermost layer. This solution runs in O(n) time and O(1) extra space.
Is Remove Outermost Parentheses asked at Google/Amazon/Meta?
This problem represents a common pattern used in technical interviews involving parentheses parsing and stack simulation. Variations of balanced parentheses processing frequently appear in interviews at companies like Amazon, Google, and Meta.
What data structure is used in Remove Outermost Parentheses?
The problem can be solved with either a simple integer counter or a stack. The counter tracks the current nesting depth of parentheses, while the stack explicitly stores opening brackets during traversal. Most optimized solutions prefer the counter because it reduces space complexity.
What is the time complexity of Remove Outermost Parentheses?
The optimal solution runs in O(n) time where n is the length of the string. Each character is processed exactly once while maintaining a simple depth counter or stack. Space complexity is O(1) for the counter approach and O(n) for the stack approach.

Ready to solve this problem?

Practice Remove Outermost Parentheses with our built-in code editor and test cases.

Practice on FleetCode
Previous

Longest Substring Without Repeating Characters

Next

Longest Palindromic Substring