Abstract / Summary

Remove the first and last parentheses and any matching pairs that enclose the whole string.

Note

The full problem description, including helpful examples, can be found on LeetCode.

This problem is ranked as

and has an acceptance rate of about 83% (300k+ submissions).

Typical patterns to solve this problem:

• Stack
• String

Every single line of code was written by me, 100% from scratch, between August 2023 and August 2024.
However, two years later I set up this website and used various AI tools to generate most of the walkthrough / explanations below.

See this dedicated page for more details.

Overview

The provided Solution class implements a method removeOuterParentheses that receives a string consisting solely of balanced parentheses. Its purpose is to strip the outermost pair of parentheses from each primitive substring while preserving the internal structure. The implementation walks through the input once, maintaining a nesting depth counter to decide which characters belong to the outer layer and should be omitted.

Core Logic

The algorithm relies on a single integer variable, depth, that reflects the current nesting level as the string is scanned from left to right. When an opening parenthesis is encountered, the depth is examined before it is incremented; when a closing parenthesis is encountered, the depth is decremented first and then examined. Characters are appended to the result only when the depth indicates that they are not part of the outermost layer.

Initialization

result = ""
depth = 0

Two variables are created: result accumulates the output, and depth tracks how deep the current position is inside nested parentheses. Both start at zero because the scan begins outside any parentheses.

Processing an Opening Parenthesis

if c == "(":
    if depth > 0:
        result += c
    depth += 1

When the current character c is '(', the code first checks whether the current depth is already greater than zero. A depth greater than zero means the parenthesis belongs to an inner level, so it is retained in result. The outermost opening parenthesis of a primitive (where depth is zero) is deliberately skipped. After the optional addition, depth is increased to reflect the new nesting level.

Processing a Closing Parenthesis

else:
    depth -= 1
    if depth > 0:
        result += c

For a closing parenthesis, the depth is reduced first because the closing symbol corresponds to the most recent opening one. If the new depth remains above zero, the closing parenthesis is part of an inner layer and is therefore appended to result. When the depth drops to zero, the closing parenthesis marks the end of a primitive and is omitted, achieving the removal of the outermost pair.

Final Return

return result

After the loop finishes, result contains the original string stripped of every outermost parenthesis pair, and it is returned to the caller.

Edge Cases Handled

The code correctly processes strings that consist of a single primitive, such as "()" or "(()())". In the case of "()", the opening parenthesis is skipped because depth is zero, and the closing parenthesis is also skipped because the depth returns to zero before the append check, resulting in an empty string, which matches the expected output.

When multiple primitives are concatenated, for example "()()" or "(()())(())", the depth resets to zero after each primitive, causing the next opening parenthesis to be treated as an outermost one and thus omitted. The algorithm therefore naturally separates primitives without additional logic.

Nested structures of arbitrary depth are also managed. Because the depth counter is incremented and decremented precisely at each parenthesis, any level of nesting is correctly identified, and only the outermost layer of each primitive is removed, regardless of how deep the inner parentheses go.

Performance Optimizations

The implementation achieves linear traversal by iterating over the input string exactly once. The use of a simple integer counter for depth eliminates the need for auxiliary data structures such as stacks, which reduces both memory overhead and constant-time operations per character. String concatenation with += is employed; in Python, repeated concatenation on a list and a final join can be faster for very large inputs, but the current approach remains efficient for typical problem constraints because each character is processed in constant time and the interpreter optimizes short-string concatenations.

By performing the depth check before modifying the counter for opening parentheses and after modifying it for closing parentheses, the code avoids extra conditional branches that would be required if the depth were examined after both increments and decrements. This ordering ensures that each character is evaluated with the minimal number of operations, contributing to a tight inner loop.

Overall, the method delivers a clean, single-pass solution with O(n) time behavior and O(1) auxiliary space, where n is the length of the input string. The absence of recursion and auxiliary containers makes the function robust for deep nesting levels without risk of stack overflow.

Imagine a row of fancy boxes that all have parentheses shaped like little curved handles. Some boxes are sitting inside other, bigger boxes. The goal is to take away the handles that are on the very outside of each group and keep only the ones tucked safely inside.

The computer starts with an empty bag to hold the pieces to keep. It also keeps track of how deep inside the boxes it is by using a number called depth. Every time a new box starts with an opening handle, the depth grows larger. If the depth is already more than zero, that means the handle is hidden inside another box, so it gets put into the bag. After that, the depth increases to show that the computer is now further inside.

When the computer sees a closing handle, the depth gets smaller because it is leaving a box. If the depth is still more than zero, it means the handle was not the final one closing the whole group, so the computer puts it into the bag too. This keeps happening until every single character in the row has been checked, leaving only the inner handles inside the bag.

Several LLMs ranked my code quality on a scale from 1 (very poor) to 10 (outstanding):

Time: linear
As a rule of thumb, the maximum input size for one second execution time is

• factorial: up to 10 elements
• exponential: up to 20 elements
• polynomial: a few thousand elements
• loglinear: up to 100,000 elements
• linear: a few million elements
• logarithmic: a billion elements
• constant: practically unlimited

I wrote a basic crawler to find other solutions to that problem.
Obviously, I did that after I solved the problem myself.

In general, AlgoMonster and WalkCCC solutions are high-quality and always worth a look.
I haven't checked most of the other solutions, but they might be helpful as well.

And of course, the LeetCode forum is always a good place (or even the best) to look for alternative approaches.

(click on a column header to sort the table)

	author
author	solutions
www	AlgoMonster	C++	Python		Java						TS
	WalkCCC	C++	Python		Java
	leetcode.ca	C++	Python		Java			Go		Rust	TS
	LeetcodeHelp	C++	Python		Java
	Progiez	C++	Python		Java
github	BigEggStudy					C#
	black-shadows	C++
	charles-wangkai				Java
	DimitrisJim								C
	everthis			JS
	fartem						Ruby
	fsq	C++
	Garvit244		Python
	halfrost							Go
	JoshCrozier			JS
	keineahnung2345	C++
	Krazune	C++
	lkwq007		Python
	lzl124631x	C++
	suxrobGM					C#
	varunu28				Java
	YuriSpiridonov		Python
AlgoMonster	C++, Python, Java, TypeScript
WalkCCC	C++, Python, Java
leetcode.ca	C++, Go, Java, Python, Rust, TypeScript
LeetcodeHelp	C++, Java, Python
Progiez	C++, Java, Python
BigEggStudy	C#
black-shadows	C++, C++
charles-wangkai	Java
DimitrisJim	C
everthis	JavaScript
fartem	Ruby
fsq	C++
Garvit244	Python
halfrost	Go
JoshCrozier	JavaScript
keineahnung2345	C++
Krazune	C++
lkwq007	Python
lzl124631x	C++
suxrobGM	C#
varunu28	Java
YuriSpiridonov	Python

There are a few extra pages giving you some insights into my setup:

• Tech Stack - my development environment and tools
• AI - how AI helped me create this website (NOT solving the problems)
• Progress - progression over time
• Quality - code quality