#1021

Easy

auto_awesomeStack-based state management

LeetCode Problem Workspace

Remove Outermost Parentheses

Remove Outermost Parentheses simplifies a valid parentheses string by removing the outermost layers of parentheses in each primitive component.

string stack

Problem Statement

Given a valid parentheses string s, the task is to remove the outermost parentheses from each primitive substring. A valid parentheses string is defined as a non-empty string of parentheses that cannot be split into smaller valid parentheses strings. The string is considered valid if it follows the structure where each opening parenthesis '(' has a matching closing parenthesis ')'.

You need to return a new string where the outer parentheses of each primitive component are removed. The string can contain nested parentheses, and your solution must account for this nesting by using an efficient approach such as a stack to manage the state of each part of the string.

Examples

Example 1

Input: s = "(()())(())"

Output: "()()()"

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

Example 2

Input: s = "(()())(())(()(()))"

Output: "()()()()(())"

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

Example 3

Input: s = "()()"

Output: ""

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.

Solution Approach

Stack-based State Management

Use a stack to traverse through the string. For each '(' character, push it onto the stack, and for each ')', check if it's the outermost parenthesis by tracking the depth of the parentheses. For every pair of parentheses, after reaching the correct depth, you can append the substring to the result, ensuring outermost parentheses are removed.

Primitive Decomposition

Identify the primitive components of the parentheses string by recognizing each part that is already fully enclosed by parentheses. Split the string into these components and remove the outermost parentheses. The challenge lies in accurately detecting the boundaries of these primitives and handling nested structures correctly.

Optimized Approach with O(n) Time Complexity

The problem can be solved in O(n) time, where n is the length of the input string. Using a single pass through the string, a stack can be used to track the depth of the parentheses, ensuring that each primitive substring is processed efficiently without the need for multiple passes.

Complexity Analysis

Metric	Value
Time	Depends on the final approach
Space	Depends on the final approach

The time complexity is O(n), where n is the length of the input string, as each character is processed once. The space complexity is O(n) due to the stack used to track parentheses depths and manage state during the process.

What Interviewers Usually Probe

The candidate efficiently manages state using a stack to handle nested structures.
The candidate demonstrates an understanding of primitive decomposition and how to handle nested parentheses.
The candidate optimizes the solution to process the string in linear time, demonstrating awareness of algorithm efficiency.

Common Pitfalls or Variants

Common pitfalls

Incorrectly handling nested parentheses, leading to the removal of incorrect parentheses.
Not accounting for strings that are already fully decomposed, resulting in an incorrect output.
Using inefficient solutions, such as multiple passes through the string, which can cause unnecessary performance overhead.

Follow-up variants

What if the input string contains only a single primitive substring with no nesting?
What if the parentheses are non-nested but the string is long?
Can this problem be solved using recursion instead of a stack?

FAQ

How do I handle nested parentheses in the Remove Outermost Parentheses problem?

Use a stack to track the opening and closing parentheses, adjusting the string based on the nesting depth to identify outermost parentheses.

What is the time complexity of solving the Remove Outermost Parentheses problem?

The time complexity is O(n), where n is the length of the input string, since we process each character once.

Can I solve the Remove Outermost Parentheses problem recursively?

Yes, recursion can be used, but it may not be as efficient as the stack-based approach for large input strings.

What is the primary pattern for solving the Remove Outermost Parentheses problem?

The primary pattern involves stack-based state management, where you track the depth of the parentheses to remove outermost layers.

What is meant by a primitive decomposition of a parentheses string?

Primitive decomposition refers to splitting the string into components where each part cannot be further divided into smaller valid parentheses strings.

terminal

Solution

Solution 1

#### Python3

1

2

3

4

5

6

7

8

9

10

11

12

13

14

class Solution:
    def removeOuterParentheses(self, s: str) -> str:
        ans = []
        cnt = 0
        for c in s:
            if c == '(':
                cnt += 1
                if cnt > 1:
                    ans.append(c)
            else:
                cnt -= 1
                if cnt > 0:
                    ans.append(c)
        return ''.join(ans)

Solution 2

#### Python3

1

2

3

4

5

6

7

8

9

10

11

12

13

14

class Solution:
    def removeOuterParentheses(self, s: str) -> str:
        ans = []
        cnt = 0
        for c in s:
            if c == '(':
                cnt += 1
                if cnt > 1:
                    ans.append(c)
            else:
                cnt -= 1
                if cnt > 0:
                    ans.append(c)
        return ''.join(ans)

Continue Practicing

#1003 check if word is valid after substitutions #1047 remove all adjacent duplicates in string #1081 smallest subsequence of distinct characters