Problem

1190. Reverse Substrings Between Each Pair of Parentheses

Insights

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

First closing bracket at index 9, switch indices with its matching opening bracket at 6

Second closing bracket at index 10, switch indices with its matching opening bracket at 3

Last closing bracket at index 13, switch indices with its matching opening bracket at 0

Algorithm

1. Scan the input string character by character, and store the indices of ( and ) in an array, where array[closingIndex] = openingIndex, array[openingIndex] = closingIndex and openingIndex and closingIndex are one pair of matching parenthese.
2. Whenever a parentheis (opening or closing) is encountered, follow the index to the matching bracket and change iteration direction.

Pseudo Code

// 1. read parenthese indices
Let N = S.length
Define an array Pairs of size N
Define a stack Stack

for i = 1 to N
   if S[i] == '('
      Stack.Push(i)
   else if S[i] == ')'
      openingIndex = Stack.Pop()
      Pairs[i] = openingIndex
      Pairs[openingIndex] = i
   else  // other characters
      // do nothing

// 2. reconstruct string
Let SS = ""

for i = 1 to N and d = 1; i += d
   if S[i] == '(' or S[i] == ')'
      i = Pairs[i]
      d *= -1
   else
      SS += S[i]

return SS

Complexity

Time - O(N). The input string is looped twice, one to read bracket indices and one to reconstruct the string. Space - O(N). A stack and a string builder are used, and they both take O(N) space.