Reverse Substrings Between Each Pair of Parentheses

class Solution {
public:
    string reverseParentheses(string str) {
        int length = str.size();
        stack<int> stackIndices;
        vector<int> pairedIndex(length);
    
        // Pairing parentheses
        for (int i = 0; i < length; ++i) {
            if (str[i] == '(') {
                stackIndices.push(i);
            }
            if (str[i] == ')') {
                int start = stackIndices.top();
                stackIndices.pop();
                pairedIndex[i] = start;
                pairedIndex[start] = i;
            }
        }
    
        // Constructing the reversed string
        string finalStr;
        for (int i = 0, step = 1; i < length; i += step) {
            if (str[i] == '(' || str[i] == ')') {
                i = pairedIndex[i];
                step = -step;
            } else {
                finalStr += str[i];
            }
        }
        return finalStr;
    }
};

The provided C++ code defines a method to reverse substrings within a string that are enclosed by pairs of parentheses. Here’s how this solution works:

• Initialize Data Structures: Creates a stack stackIndices to store the index of each '(' and a vector pairedIndex to store the paired index of each parenthesis.
• Pair Parentheses: Iterates through the input string str. For every '(', it pushes the current index onto stackIndices. For every ')', it pops the top index from stackIndices (this represents the matching '('), and records the indices in pairedIndex where the opening and closing brackets correspond.
• Construct Reversed String: Begins another iteration of the string, using a variable step to control navigation (forward or reversed). If the current character is a parenthesis, it switches direction and jumps to the paired parenthesis index as per pairedIndex. If it's not a parenthesis, it appends the character to the result string finalStr.

This algorithm effectively manages the reversal of contents within each set of parentheses, leveraging stack for tracking the pairing and a vector for direct access to paired indices, ensuring an efficient construction of the final string with sections reversed as required.

public class Solution {
    
    public String reverseStringInParentheses(String inputStr) {
        int length = inputStr.length();
        Stack<Integer> stack = new Stack<>();
        int[] reverseIndices = new int[length];
    
        // Match opening and closing parentheses
        for (int i = 0; i < length; ++i) {
            if (inputStr.charAt(i) == '(') {
                stack.push(i);
            }
            if (inputStr.charAt(i) == ')') {
                int start = stack.pop();
                reverseIndices[i] = start;
                reverseIndices[start] = i;
            }
        }
    
        // Construct reversed string based on parentheses
        StringBuilder output = new StringBuilder();
        for (
            int index = 0, step = 1;
            index < length;
            index += step
        ) {
            if (inputStr.charAt(index) == '(' || inputStr.charAt(index) == ')') {
                index = reverseIndices[index];
                step = -step;
            } else {
                output.append(inputStr.charAt(index));
            }
        }
    
        return output.toString();
    }
}

Reverse a substring between each pair of parentheses in a given string using Java. The solution utilizes a stack to track the indices of the parentheses and an array to record the corresponding reverseIndices, facilitating the reversal process.

• Initialize a Stack<Integer> to keep track of the index of each '(' encountered.
• Traverse the input string. For each character:
  • Push index onto stack if character is '('.
  • If character is ')', pop from stack to get the start index of '(', and update reverseIndices for start and current index.
• Using a StringBuilder, build the output string:
  • Iterate over the string. If a '(' or ')' is encountered, use reverseIndices to jump to the corresponding match and reverse the traversal direction.
  • Add characters to StringBuilder unless at parentheses, effectively skipping them and adding only the reversed substrings.
• Return the resulting string from StringBuilder.

This method efficiently handles nested and multiple successive parentheses by directly manipulating indices and using a StringBuilder to accumulate the results.

class Solution:
    def reverseParentheses(self, input_string: str) -> str:
        length = len(input_string)
        stack = []
        indices_map = [0] * length
    
        # Link matching parentheses indices
        for current_position in range(length):
            if input_string[current_position] == "(":
                stack.append(current_position)
            elif input_string[current_position] == ")":
                opening_position = stack.pop()
                indices_map[current_position] = opening_position
                indices_map[opening_position] = current_position
    
        # Construct output by navigating linked indices
        output = []
        index = 0
        step = 1
    
        while index < length:
            if input_string[index] == "(" or input_string[index] == ")":
                index = indices_map[index]
                step = -step
            else:
                output.append(input_string[index])
            index += step
    
        return "".join(output)

This solution effectively reverses the substrings that lie between each pair of parentheses in a given string. The implementation commences by initializing a stack to keep track of the opening parenthesis indices and an array indices_map to link the positions of corresponding opening and closing parentheses. As the string is traversed:

• When an opening parenthesis is encountered, its index is pushed onto the stack.
• When a closing parenthesis is encountered, the index of its matching opening parenthesis is popped from the stack, and both indices are linked in the indices_map.

After establishing these links, the string is reconstructed by navigating through the linked indices. This redirection through the string is controlled by the index variable, which moves forward or backward (step), ensuring correct sequence assembly:

• When a parenthesis is encountered during reconstruction, the traversal direction is switched (by flipping the sign of step) and jumps to its linked counterpart index.
• Non-parenthetical characters are collected into the output list.

The function eventually returns the reconstructed string, which contains all nested and sequenced reversals correctly applied. This approach avoids deep nested loops and efficiently handles the reversal using stack-based linking and direction-flipping techniques, providing an optimal and elegant solution to the problem.