algoadvance

Leetcode Problem 1021: Remove Outermost Parentheses

A valid parentheses string is either empty "", "(" + A + ")", or A + B, where A and B are valid parentheses strings, and + represents string concatenation. For example, "", "()", "(())()", and "(()(()))" are all valid parentheses strings.

A valid parentheses string S is primitive if it is non-empty, and there does not exist a way to split it into S = A + B, with A and B non-empty valid parentheses strings.

Given a valid parentheses string S, consider its primitive decomposition: S = P_1 + P_2 + ... + P_k, where P_i are primitive valid parentheses strings.

Return S after removing the outermost parentheses of every primitive string in the primitive decomposition of S.

Example

Input: "(()())(())"
Output: "()()()"
Explanation: 
The input is broken into primitive strings as follows:
- (()())
- (())
Removing the outermost parentheses of each part ends up with:
- ()()
- () 
So the final result is ()()().

Clarifying Questions:

  1. Q: Will the input string always be a valid parentheses string? A: Yes, the problem guarantees that the input string is always a valid parentheses string.

  2. Q: What is the length range of the input string? A: The length of the string is guaranteed to be between 1 and 10,000.

Strategy

  1. Use a counter to keep track of the depth of the parentheses.
  2. Initialize an empty list result to build the final string.
  3. Iterate through the input string:
    • If encountering an opening parenthesis ( and the depth counter is greater than 0, add it to the result list (to avoid adding the outermost ().
    • If encountering a closing parenthesis ) and the depth counter is greater than 1, add it to the result list (to avoid adding the outermost )).
    • Adjust the depth counter as you encounter each parenthesis.
  4. Join and return the result list as a string.

Code

def removeOuterParentheses(S: str) -> str:
    result = []
    depth = 0
    
    for char in S:
        if char == '(':
            if depth > 0:
                result.append(char)
            depth += 1
        elif char == ')':
            depth -= 1
            if depth > 0:
                result.append(char)
    
    return ''.join(result)

Time Complexity

This solution is efficient and meets the problem requirements. It ensures that the outermost parentheses of each primitive string are removed as specified.

Try our interview co-pilot at AlgoAdvance.com