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 <= 2000s only contains lower case English characters and parentheses.To solve #1190 Reverse Substrings Between Each Pair of Parentheses, the key challenge is handling nested parentheses while reversing only the characters inside them. A natural way to manage nested structures is by using a stack.
Iterate through the string character by character. When you encounter an opening parenthesis (, push the current accumulated string onto a stack and start building a new substring. When a closing parenthesis ) appears, reverse the current substring and append it to the string stored at the top of the stack. This effectively processes the innermost parentheses first, which matches the required behavior.
An alternative optimized approach precomputes matching parenthesis indices and traverses the string while dynamically changing direction. Both strategies ensure correct handling of deeply nested parentheses.
The stack-based approach runs in O(n) time where n is the string length, with O(n) auxiliary space for the stack and intermediate strings.
| Approach | Time Complexity | Space Complexity |
|---|---|---|
| Stack-based substring construction | O(n) | O(n) |
| Precomputed parenthesis mapping with directional traversal | O(n) | O(n) |
NeetCodeIO
Use these hints if you're stuck. Try solving on your own first.
Find all brackets in the string.
Does the order of the reverse matter ?
The order does not matter.
Utilize a stack to handle the nested or paired parentheses efficiently. By pushing characters onto a stack until a closing parenthesis is encountered, then reversing the needed substring, you can leverage the stack's LIFO properties to achieve the desired result.
Time Complexity: O(n).
Space Complexity: O(n) due to the stack usage for storing characters.
1#include <stdio.h>
2#include <string.h>
3#include <stdlib.h>
4
5char* reverseParentheses(char* s) {
This C solution uses an array-based stack to reverse substrings between parenthesis pairs. It iterates through the string, storing characters inside a stack until a closing parenthesis requires a substring reversal. The reversed substring is then pushed back onto the stack, achieving the desired sequence without parentheses.
This approach involves separately building the result string in a single pass using an auxiliary data structure to track position swaps. The use of local in-string reversals enables an efficient and clean traversal building mechanism.
Time Complexity: O(n).
Space Complexity: O(n), using additional space for parentheses pair tracking and intermediate char arrays.
1
Watch expert explanations and walkthroughs
Practice problems asked by these companies to ace your technical interviews.
Explore More ProblemsJot down your thoughts, approach, and key learnings
Yes, an optimized approach maps each pair of parentheses and traverses the string while switching traversal direction when a parenthesis is hit. This avoids repeated string reversals and still achieves linear time complexity.
Yes, variations of this problem appear in technical interviews because it tests string manipulation, stack usage, and handling nested structures. Companies often use similar problems to evaluate problem-solving with stacks and parsing logic.
A stack is the most suitable data structure because it naturally supports nested structures like parentheses. It allows you to temporarily store previous substrings and correctly rebuild the result when a closing parenthesis is encountered.
The most common optimal approach uses a stack to handle nested parentheses. When encountering a closing parenthesis, the current substring is reversed and combined with the previous string from the stack. This ensures inner parentheses are processed before outer ones.
This C solution divides the task into first creating pair indices for easy traversal and reversal through position swapping, enabling an efficient processing path that aligns with the stack-based idea but applied to index transformations and direct character use.