{x}
blog image

Reverse Substrings Between Each Pair of Parentheses

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.

 

Example 1:

Input: s = "(abcd)"
Output: "dcba"

Example 2:

Input: s = "(u(love)i)"
Output: "iloveu"
Explanation: The substring "love" is reversed first, then the whole string is reversed.

Example 3:

Input: s = "(ed(et(oc))el)"
Output: "leetcode"
Explanation: First, we reverse the substring "oc", then "etco", and finally, the whole string.

 

Constraints:

  • 1 <= s.length <= 2000
  • s only contains lower case English characters and parentheses.
  • It is guaranteed that all parentheses are balanced.

Solution Explanation for Reversing Substrings Between Parentheses

This problem requires reversing substrings enclosed within parentheses, starting from the innermost pairs. The solutions presented use different approaches: a stack-based simulation and a more optimized approach leveraging a mapping array.

Approach 1: Stack-Based Simulation

This approach uses a stack to track characters. When a closing parenthesis ) is encountered, it pops characters from the stack until an opening parenthesis ( is found. The popped characters (the substring within the parentheses) are then reversed and pushed back onto the stack. Finally, the stack's contents are joined to form the result.

Algorithm:

  1. Initialize an empty stack stk.
  2. Iterate through the input string s:
    • If the character is ):
      • Create an empty list t.
      • Pop characters from stk and append them to t until an ( is encountered.
      • Discard the (.
      • Extend stk with the reversed t.
    • Otherwise (character is not )):
      • Push the character onto stk.
  3. Return the string formed by joining the elements in stk.

Time Complexity: O(n^2) - In the worst case (e.g., deeply nested parentheses), the reversal process within the inner loop can take O(n) time for each parenthesis pair, leading to a quadratic time complexity.

Space Complexity: O(n) - The stack can hold up to n characters in the worst case.

Approach 2: Optimized Approach with Mapping Array

This approach is more efficient. It first creates a mapping array d where d[i] stores the index of the matching parenthesis for the parenthesis at index i. Then, it iterates through the string, using the mapping array to efficiently jump between matching parentheses and reverse the traversal direction as needed.

Algorithm:

  1. Create a mapping array d of size n (length of the string). Use a stack to find matching parentheses indices. d[i] will hold the index of the matching parenthesis for the parenthesis at index i.
  2. Initialize i (current index) to 0 and x (traversal direction) to 1.
  3. Iterate until i reaches the end of the string:
    • If the current character is a parenthesis:
      • Update i to the index of its matching parenthesis using d[i].
      • Reverse the traversal direction (x = -x).
    • Otherwise (character is not a parenthesis):
      • Append the character to the result.
    • Update i based on the traversal direction (i += x).
  4. Return the resulting string.

Time Complexity: O(n) - The algorithm iterates through the string at most twice (once to create the mapping and once to build the result).

Space Complexity: O(n) - The mapping array d and potentially the stack used to build it require O(n) space.

Code Examples (Python, Java, C++, Go, TypeScript, Javascript)

The code examples for both approaches are provided in the original response, demonstrating their implementation in various programming languages. The optimized approach (Approach 2) provides a significant performance improvement compared to the simulation approach (Approach 1), especially for long strings with deeply nested parentheses.