Last Updated: 25 Apr, 2021
Reverse Substrings Between Each Pair of Parentheses
Moderate
Asked in company
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
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
Approaches
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.
A possible solution to this problem could be to use a stack. First, check whenever a ‘(‘ is encountered, and push the index of that element into the stack and whenever a ‘)’ is encountered, then get the top element of the stack as the latest index and reverse the string between the current index and index from the top of the stack. Follow this for the rest of the string and finally print the updated string.
The algorithm to calculate the required will be:-
- Initialize a stack ‘STACK’ to store indices of ‘(’ the parentheses.
- Now, traverse the given string ‘S’:
- If S[i] == ‘(’.
- Push the index of the given string that has the value of starting parentheses ‘(‘ i.e. push the index of the current opening bracket.
- If S[i] == ‘)’.
- Reverse the substring starting after the last encountered opening bracket till the current character ‘)’ is reached and pop the topmost element of the stack.
- If S[i] == ‘(’.
- Now store the modified string obtained from the reversal ignoring all the parentheses present in the string and only keeping the other characters in ‘ANS’.
- Finally, return the result ‘ANS’.