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

SimplyLeet
TagsCompaniesDisclaimersPrivacyTermsContactAbout Us

Reverse Substrings Between Each Pair of Parentheses

Number: 1298

Difficulty: Medium

Paid? No

Companies: Bloomberg, Microsoft, Google, Amazon, Agoda, Goldman Sachs, Adobe

Problem Description

Given a string s containing lower-case English letters and balanced parentheses, reverse the substrings contained within each pair of matching parentheses, starting from the innermost pair. The final output should not include any parentheses.

Key Insights

  • Use a stack to keep track of the substrings before encountering a parenthesis.
  • When an opening bracket '(' is encountered, push the current working substring onto the stack and reset it.
  • When a closing bracket ')' is encountered, reverse the current substring and then append it to the substring obtained from the top of the stack.
  • This approach naturally handles nested parentheses by processing the innermost substring first.

Space and Time Complexity

Time Complexity: O(n), where n is the length of the input string. Space Complexity: O(n), due to the use of a stack to store intermediate substring states.

Solution

We solve the problem by iterating through the string character by character. We maintain a "current" container (using a list or similar structure) to build the substring under processing. When encountering an opening parenthesis, we push the current substring onto a stack and reset it for building the new substring. When we encounter a closing parenthesis, we reverse the current substring, then pop the previous substring state from the stack and concatenate the reversed substring to it. This method ensures that nested parentheses are correctly handled, and at the end, we obtain a string without any remaining parentheses.

Code Solutions

def reverseParentheses(s: str) -> str:
    # Initialize a stack to store previous substrings
    stack = []
    # Use a list to efficiently build the current substring
    current = []
    
    # Iterate over each character in the string
    for char in s:
        if char == '(':
            # Push the current substring onto the stack
            stack.append(current)
            # Reset current substring for the new sequence
            current = []
        elif char == ')':
            # Reverse the current substring when a closing parenthesis is found
            current.reverse()
            # Pop the last substring from the stack and combine
            current = stack.pop() + current
        else:
            # Append regular characters to the current substring
            current.append(char)
    
    # Join the list into a string and return the final result
    return "".join(current)

# Example usage:
print(reverseParentheses("(u(love)i)"))  # Output: iloveu
← Back to All Questions