Introduction

In this blog post, we will explore how to solve the LeetCode problem "1190" using AI. LeetCode is a popular platform for preparing for coding interviews, and with the help of AI tools like Chatmagic, we can generate solutions quickly and efficiently - helping you pass the interviews and get the job offer without having to study for months.

Problem Statement

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.

Explanation

Here's a breakdown of the solution approach, followed by the code:

• Find Matching Parentheses: Use a stack to efficiently determine the matching parenthesis for each index in the string. This helps to quickly identify the substrings that need to be reversed.

• Iterate and Reverse: Traverse the string, and when you encounter an opening parenthesis, jump to its matching closing parenthesis using the precomputed mapping. Reverse the substring between them. When encountering a closing parenthesis, jump back to its matching opening parenthesis. This simulates reversing from the innermost to the outermost pairs.

• Build Result: Construct the final string by skipping the parenthesis and including the reversed substrings.

• Time & Space Complexity: O(n) time complexity, O(n) space complexity

Code

    def reverse_parentheses(s: str) -> str:
    """
    Reverses the strings in each pair of matching parentheses, starting from the innermost one.

    Args:
        s: The input string.

    Returns:
        The string with reversed parentheses.
    """

    n = len(s)
    pair = {}
    stack = []

    for i, char in enumerate(s):
        if char == '(':
            stack.append(i)
        elif char == ')':
            j = stack.pop()
            pair[i] = j
            pair[j] = i

    res = ""
    i = 0
    d = 1  # Direction: 1 for forward, -1 for backward

    while i < n:
        if s[i] == '(':
            i = pair[i]
            d *= -1
            i += d
        elif s[i] == ')':
            i = pair[i]
            d *= -1
            i += d
        else:
            res += s[i]
            i += d

    return res