1190. Reverse Substrings Between Each Pair of Parentheses

• 1190-Reverse-Substrings-Between-Each-Pair-of-Parentheses.org
• submission: Reverse Substrings Between Each Pair of Parentheses

Given a string `s` which consists of lowercase English letters and brackets. Reverse substrings that are in each pair of matching parentheses from the innermost one to the outermost one, and return the resulting string without any parentheses.

For example:

Input: `s = "(ab(cd)e)"`
Output: `s = "edcba"`

To implement the solution, we need to use a stack to manage the parentheses and the nested substrings efficiently.

1. Create an empty stack to keep track of characters.
2. Traverse the string character by character.
3. If an open parenthesis `(` is encountered, push it onto the stack.
4. If a closing parenthesis `)` is encountered, start popping from the stack until an open parenthesis `(` is found. Reverse the collected characters and push them back onto the stack.
5. After processing the entire string, the stack should contain the final result in the correct order. We then convert the stack to a string.

The time complexity is O(n) because we traverse the string twice (one push and one pop per character), where n is the length of the string. The space complexity is also O(n) because we store the characters in the stack.

Consider the input `s = "(u(love)i)"`.

1. Traverse and push `(`, `u`.
2. Push `(` again.
3. Traverse and push `l`, `o`, `v`, `e`.
4. Pop until `(`, reverse `love` to `evol`, and push characters back.
5. Continue pushing `i`, `)`.
6. Pop until `(`, reverse `uevoli` to `iloveu`.
The final stack holds `iloveu`.

Below is the JavaScript function implementing the described solution, along with a set of test cases.

/**
 * @param {string} s - Input string containing lowercase English letters and parentheses
 * @returns {string} - Final string after reversing substrings within parentheses
 */
function reverseParentheses(s) {
    const log = typeof NestedInteger !== 'undefined' ? () => {} : console.log;
    const table = typeof NestedInteger !== 'undefined' ? () => {} : console.table;

    const stack = [];

    for (const ch of s) {

        if (ch !== ')') {
            stack.push(ch);
        } else {
            let tmp = '';
            while (stack.length && stack[stack.length - 1] !== '(') {
                tmp += stack.pop();
            }
            stack.pop(); // remove the (

            for (const char of tmp) {
                stack.push(char);
            }
        }
    }

    return stack.join('');
}

// Test cases
const testCases = [
    { input: "(ed(et(oc))el)", expected: "leetcode"},
    { input: "(ab(cd)e)", expected: "ecdba" },
    { input: "(u(love)i)", expected: "iloveu" },
    { input: "a(bc(de)fg)", expected: "agfdecb" },
    { input: "((abc)def)", expected: "fedabc" },
    { input: "a(bc)de", expected: "acbde" },
];

testCases.forEach((test, index) => {
    const result = reverseParentheses(test.input);
    console.log(`Test Case ${index + 1}: ${result === test.expected ? 'Passed' : 'Failed'} (Expected: ${test.expected}, Got: ${result})`);
});