PPractick

The problem

A code formatter receives a valid parentheses string made of several primitive groups (non-empty balanced groups that can't be split further), such as (()()) followed by (()). The formatter should strip the outermost pair from each primitive group, keeping everything inside. The neat observation: a parenthesis is outermost exactly when it opens a group at depth 0 or closes one back to depth 0. So a single pass with a depth counter decides for every character whether to keep it, with no stack or splitting needed.

Example: "(()())(())" → "()()()".

Function signature

string removeOuterParentheses(const string& s);  // s is a valid parentheses string

Test cases

Input s	Output	Explanation
"(()())(())"	"()()()"	Primitives (()()) and (()) become ()() and ()
"(()())(())(()(()))"	"()()()()(())"	Three primitives
"()()"	""	Each primitive is just ()
"(())"	"()"
"((()))"	"(())"

(Confirm: the input is always valid; only the outermost pair of each primitive group is removed.)

How interviewers phrase it

• "Remove the outermost parentheses of every primitive string" (LeetCode 1021).
• A warm-up for parentheses problems: valid parentheses, maximum nesting depth (S.No 142), minimum additions to make valid.

Clarifying questions to ask

1. Is the input guaranteed to be valid?
2. Only ( and ), or other bracket types too?
3. Should the result be a new string?

Follow-ups to expect

1. "How do you know a parenthesis is outermost?"
2. "Do you need a stack?"
3. "How would you split the string into primitives?"
4. "What if the string could be invalid?"
5. "Complexity?"

Related questions

• Maximum Nesting Depth of the Parentheses Medium
• Infix to Postfix Conversion Medium
• Prefix to Infix Conversion Medium
• Prefix to Postfix Conversion Medium
• Postfix to Prefix Conversion Medium
• Infix to Prefix Conversion Medium

All 474 dsa interview questions

DSA mock interviews · System design interview questions · Free mock interview practice · Browse interviewers · Sign in