Reverse Substrings Between Each Pair Of Parentheses - Leetcode Solution

Problem Description:

Given a string s that consists of lowercase English letters and brackets. Reverse the strings in each pair of matching parentheses, starting from the innermost one.

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

Input: s = "(u(love)i)" Output: "iloveu"

Input: s = "(ed(et(oc))el)" Output: "leetcode"

Input: s = "a(bcdefghijkl(mno)p)q" Output: "apmnolkjihgfedcbq"

Solution:

We can approach this problem using a stack data structure. We iterate through each character in the given string, and once we encounter an opening parenthesis, we push the current string onto the stack and reset the current string. Once we encounter a closing parenthesis, we pop the topmost element from the stack and reverse the current string. We then append the reversed string to the string below it in the stack.

We also keep a boolean variable to track if we are currently inside a pair of parentheses or not. If we are, we do not append the current character to the current string, since we will be reversing it anyways.

Finally, we return the modified string after we have processed all characters.

Here's the Python code to implement this algorithm:

def reverseParentheses(s): stack = [] currStr = "" insideParentheses = False for c in s: if c == "(": stack.append(currStr) currStr = "" insideParentheses = True elif c == ")": prevStr = stack.pop() currStr = prevStr + currStr[::-1] insideParentheses = False else: if not insideParentheses: prevStr = currStr currStr = prevStr + c else: currStr += c return currStr

Time Complexity:

The time complexity of this algorithm is O(N^2), where N is the length of the input string. This is because we use string concatenation in each iteration, which takes O(N) time. In the worst-case scenario, each character could be enclosed in a pair of parentheses, meaning we would need to concatenate the strings N/2 times, resulting in the overall time complexity of O(N^2). However, in practice, the number of parentheses pairs is likely to be much smaller, resulting in a significantly lower running time.

Space Complexity:

The space complexity of the algorithm is O(N), where N is the length of the input string. This is due to the fact that we create a stack containing all the strings enclosed in parentheses, which could add up to a maximum of N/2 strings. Additionally, the current string variable and the boolean variable both take up constant space.

1