We use cookies (including Google cookies) to personalize ads and analyze traffic. By continuing to use our site, you accept our Privacy Policy.

SimplyLeet
TagsDisclaimersPrivacyTermsContactAbout Us

Reverse Substrings Between Each Pair of Parentheses

Difficulty: Medium

Problem Description

You are given a string s that consists of lower case English letters and brackets. Reverse the strings in each pair of matching parentheses, starting from the innermost one. Your result should not contain any brackets.

Key Insights

  • The problem involves reversing substrings within pairs of parentheses.
  • The innermost parentheses must be processed first, requiring a method to track nested parentheses.
  • A stack data structure is suitable for this task, as it allows us to reverse substrings in the correct order.

Space and Time Complexity

Time Complexity: O(n)
Space Complexity: O(n)

Solution

To solve this problem, we can use a stack to keep track of characters as we iterate through the string. When we encounter an opening parenthesis '(', we push the current substring onto the stack and start a new substring. When we find a closing parenthesis ')', we reverse the current substring and append it to the substring popped from the stack. This approach ensures that we handle the innermost parentheses first, effectively allowing us to build up the final result without any parentheses remaining.

Code Solutions

def reverseParentheses(s: str) -> str:
    stack = []
    current_string = []
    
    for char in s:
        if char == '(':
            # Push current string to stack and start a new one
            stack.append(current_string)
            current_string = []
        elif char == ')':
            # Reverse current string and merge with the last string from stack
            current_string.reverse()
            last_string = stack.pop()
            last_string.extend(current_string)
            current_string = last_string
        else:
            # Append character to current string
            current_string.append(char)
    
    return ''.join(current_string)
← Back to All Questions