Show problems as
Classic problem #1021EasyStringStackBracket Sequences

Remove Outermost Parentheses

Real-world version: Strip Root Frame Markers
Tracked in this browser only
Read Remove Outermost Parentheses on LeetCode(opens in a new tab)

The statement here is our own: the same inputs, outputs and technique.

A sampling profiler writes one character every time control moves: ( when a function is entered and ) when it returns. The finished tape trace is therefore balanced, and it splits into root frames: a root frame is a balanced chunk of the tape that is not contained in any longer balanced chunk, so reading the tape left to right and cutting every time the open-count falls back to zero recovers the root frames in order.

The viewer already draws each root frame as its own row, so the pair of markers that encloses a root frame is redundant. Build the trimmed tape: take every root frame, drop its first and its last character, and concatenate what is left in the original order.

Return the trimmed tape as a string. It may be empty.

Examples

Example 1

Input
s = "(())(()())"
Output
"()()()"

The root frames are `(())` and `(()())`. Dropping the enclosing pair of each leaves `()` and `()()`, which join to `()()()`.

Example 2

Input
s = "((()))"
Output
"(())"

The whole tape is a single root frame, so only its first and last characters go away.

Example 3

Input
s = "()(())"
Output
"()"

The root frames are `()` and `(())`; the first contributes nothing and the second contributes `()`.

Example 4

Input
s = "(()(()))()"
Output
"()(())"

The root frames are `(()(()))` and `()`; the first contributes `()(())` and the second contributes nothing.

Constraints

  • 1 <= s.length <= 10^5
  • s[i] is either '(' or ')'.
  • s is balanced: every '(' has a matching ')' after it and the open-count never drops below zero.

The signature

The editor starts with this. It matches the parent problem's shape, so a solution that works here works on a standard judge unchanged.

Python
def strip_frame_markers(trace: str) -> str:
Java
public String stripFrameMarkers(String trace)

More on the same topics