Reverse Substrings Between Each Pair of Parentheses

Moderate
0/80
Average time to solve is 15m
profile
Contributed by
6 upvotes
Asked in company
SAP Labs

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 : 
Suppose the given string ‘S’ is ‘((ng)ipm(ca))’ then the resultant reversed string on removing the parentheses here is ‘camping’ which can be done in the following steps:

-> ((ng)ipm(ca))
-> (gnipmac)
-> camping
Detailed explanation ( Input/output format, Notes, Images )
Input Format : 
The first line of input contains a single integer ‘T’ denoting the number of test cases given. Then next ‘T’ lines follow:

The first line of each test case input contains the length ‘N’ of the given string input ‘S’.

The second line of each test case input contains the given string input with matching parentheses ‘S’.
Output Format : 
For every test case, return the final reversed string after reversing successive strings in each pair of matching parentheses, starting from the innermost one without any brackets.
Note : 
You do not need to print anything; it has already been taken care of. Just Implement the given function.
Constraint : 
1 <= ‘T’ <= 100
1 <= ‘N’ <= 1000
‘S’ contains only lowercase alphabets, ‘(‘ and ‘)’.

Where ‘T’ is the number of test cases given for the problem,  ‘N’ is the length (‘S’.length) of the given string ‘S’. It's guaranteed that all parentheses are balanced.


Time Limit: 1 sec
Sample Input 1 :
2
10
(u(love)i)
18
(sajn(i(gn)ni)doc)
Sample output 1 :
iloveu
codingninjas
Explanation :
Test Case 1 :

The output “iloveu” is the required reversed string ‘S’ after removing the given set of parentheses in the string. Here, the substring "love" is reversed first, then the whole string is reversed, 
-> (u(love)i) 
-> (uevoli)
-> iloveu


Test Case 2 :

The output “codingninjas” is the required string ‘S’ after removing the given set of parentheses in the string. Here, the substring "gn" is reversed first, then “ingni”, and finally, the whole string is reversed, 

-> (sajn(i(gn)ni)doc) 
-> (sajn(ingni)doc) 
-> codingninjas
Sample Input 2 :
2
21
a(bcdefghijkl(mno)p)q
13
((ng)ipm(ca))
Sample output 2 :
apmnolkjihgfedcbq
camping
Hint

Try to use strings to save different substrings in a pair of matched brackets and a stack to save those strings.

Approaches (2)
Brute Force

A possible solution to this problem could be to use a stack initialized by pushing an empty string. First, check whenever a ‘(‘ is encountered. Push another empty string in that case into the stack, and whenever a ‘)’ is encountered, then get the top element of the stack and reverse the string that is stored at the top of the stack. Append that reversed string to the remaining element that is now on top of the stack and update that with this. Else if the character is neither '(' nor ‘)’, update the top of the stack by appending the character to the string that is presently on top. Follow this for the rest of the string and finally pop the top of the stack and print the updated string. 

 

The algorithm to calculate the required will be:-

 

  • Initialize a stack ‘STACK’ to store the strings between the parentheses initially pushing an empty string in it.
  • Now, traverse the given string ‘S’ and keep pushing empty strings until starting parentheses ‘(‘ is encountered.
  • If closing parentheses ')' is encountered then pop the top element of the stack and reverse the string. After this, we can still get another element that is on top, append the reversed string to this top element and update the top with this string.
  • If the encountered string is neither a “(” or “)“ then get the top string element of the stack and append the character to it and push the updated string back into the stack.
  • Finally, pop the top string element in the stack and return the result.
Time Complexity

O(N^2), where ‘N’ is the length of the given string ‘S’.

 

We are iterating over all the characters of the string ‘S’, and in every iteration (which is of order O(‘N’)) there is a string reversal taking place (which has a worst-case complexity of O(N)) hence, the complexity here grows by O(N^2).

Space Complexity

O(N), where ‘N’ is the length of the given string ‘S’.

 

Since we are storing strings of lengths up to size ‘N’ in our stack that we are using, therefore, the space complexity is O(N).

Code Solution
(100% EXP penalty)
Reverse Substrings Between Each Pair of Parentheses
Full screen
Console