Abstract / Summary

Reverse the text inside each pair of parentheses and handle nested parentheses by reversing the innermost first.

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 72% (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 implementation defines a class Solution with a single method reverseParentheses. The method receives a string that may contain lowercase letters and pairs of parentheses. Its purpose is to return a new string where the characters inside each pair of parentheses are reversed, and the parentheses themselves are removed. The algorithm processes the input in a single left-to-right pass, using a stack to keep track of the current building segment.

Core Logic

The algorithm begins by initializing a stack that holds strings. The first element of the stack is an empty string, representing the outermost level that will accumulate the final result.

stack = [ "" ]

The main loop iterates over each character c in the input string s. Three distinct branches handle the possible character types:

1. When the character is an opening parenthesis '(', a new empty string is pushed onto the stack. This marks the start of a new nested segment whose characters will be collected separately.

if c == "(":
    stack.append("")

2. When the character is a closing parenthesis ')', the most recent segment is popped from the stack, reversed, and concatenated to the string that now resides at the top of the stack. This effectively collapses the innermost parentheses, applying the required reversal.

elif c == ")":
    last = stack.pop()
    stack[-1] += last[::-1]

3. For any other character (letters or other non-parenthesis symbols), the character is appended to the string at the top of the stack, building the current segment.

else:
    stack[-1] += c

After the loop finishes, the stack contains a single element-the fully processed string without any parentheses. The method returns this element.

return stack[-1]

Edge Cases Handled

The design naturally accommodates several edge conditions without additional checks:

• Empty Input - When s is an empty string, the loop body never executes. The stack remains [ "" ], and the method returns an empty string, correctly reflecting the absence of content.

• No Parentheses - If the input contains no '(' or ')', every character falls into the third branch, appending directly to the initial stack element. The final return yields the original string unchanged, as required.

• Nested Parentheses - The stack structure inherently supports arbitrarily deep nesting. Each '(' pushes a new buffer, and each ')' pops the most recent buffer, reverses it, and merges it upward. This ensures that inner reversals are applied before outer ones, matching the expected semantics.

• Consecutive Parentheses - Sequences such as "()()" generate empty buffers for each pair. When a closing parenthesis is encountered, the popped empty string reverses to an empty string and concatenates harmlessly to the outer buffer, effectively discarding the empty parentheses.

• Unbalanced Parentheses - The algorithm assumes well-formed input; however, the stack operations would raise an exception if a closing parenthesis appears without a matching opening one, or if extra opening parentheses remain after processing. This behavior aligns with the typical contract that the input is guaranteed to be balanced.

Performance Characteristics

The implementation processes each character exactly once, performing only constant-time operations per character: a stack push, a stack pop, a string concatenation, or a slice reversal. The use of Python’s slice notation [::-1] creates a reversed copy of the current segment in linear time relative to the segment’s length, but because each character participates in at most one reversal (the one associated with its innermost enclosing parentheses), the total amount of work across all reversals remains proportional to the length of the input.

String concatenation is performed on the mutable top-of-stack buffer. Since each buffer is built incrementally and only concatenated to its parent after reversal, the number of concatenations per character is limited, avoiding the quadratic blow-up that can occur when repeatedly concatenating to a single immutable string.

The stack itself grows only as deep as the maximum nesting level of parentheses, which is bounded by the length of the input. Memory usage therefore scales linearly with the input size, with each character stored exactly once in some buffer.

Overall, the algorithm delivers efficient linear-time processing with modest auxiliary memory, leveraging Python’s built-in string operations and a straightforward stack discipline to achieve the required transformation.

Imagine there is a big box that holds little boxes inside it. This code starts with one empty box to hold the letters of a word. When a tiny opening parenthesis appears, it is like placing a brand new empty box inside the current one to start a fresh pile.

When a character shows up that is just a regular letter, it gets added right into the box that is sitting on the very top of the pile.

The most exciting part happens when a closing parenthesis shows up. That tells the computer to take the top box off the pile and flip all the letters inside backward, just like magic. Then, those flipped letters are put into the next box down in the stack to join the others. By the time the code reaches the end of the word, all the letters have been moved around and turned inside out exactly where they belong.

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

not analyzed yet

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	JS	Java		Go	TS
	MemoryLimitExceeded	C++	Python
	Progiez	C++	Python		Java
github	BigEggStudy					C#
	black-shadows	C++
	charles-wangkai				Java
	everthis			JS
	fpdjsns	C++
	fsq	C++
	Garvit244		Python
	halfrost						Go
	JoshCrozier			JS
	keineahnung2345	C++
	lkwq007		Python
	suxrobGM					C#
	varunu28				Java
	wisdompeak	C++
AlgoMonster	C++, Python, Java, TypeScript
WalkCCC	C++, Python, Java
leetcode.ca	C++, Go, Java, JavaScript, Python, TypeScript
MemoryLimitExceeded	Python, C++
Progiez	C++, Java, Python
BigEggStudy	C#
black-shadows	C++, C++
charles-wangkai	Java
everthis	JavaScript
fpdjsns	C++
fsq	C++
Garvit244	Python
halfrost	Go
JoshCrozier	JavaScript
keineahnung2345	C++
lkwq007	Python
suxrobGM	C#
varunu28	Java
wisdompeak	C++

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