Leetcode 1190: Reverse Substrings Between Each Pair of Parentheses
Given a string containing lowercase English letters and balanced parentheses, reverse the substrings enclosed within each pair of parentheses, starting from the innermost ones. After processing, return the resulting string without any parentheses.
Problem
Approach
Steps
Complexity
Input: A single string `s` containing lowercase English letters and parentheses. Parentheses in the string are guaranteed to be balanced.
Example: Input: s = "(xy(z))"
Constraints:
• 1 <= s.length <= 2000
• s only contains lowercase English characters and parentheses.
• All parentheses are guaranteed to be balanced.
Output: A string representing the final processed version of `s` after reversing all substrings enclosed in parentheses and removing the parentheses.
Example: Output: "zyx"
Constraints:
• The output string must not contain any parentheses.
• The order of characters must be correct after processing.
Goal: To reverse substrings enclosed within matching parentheses from the innermost to the outermost and return the processed string without parentheses.
Steps:
• Iterate through the string and process characters.
• Push the indices of opening parentheses onto a stack.
• When encountering a closing parenthesis, reverse the substring from the last opening parenthesis to the current position.
• Remove parentheses and construct the final string.
Goal: The problem has a well-defined input size and structure, ensuring efficient processing.
Steps:
• The input string can be up to 2000 characters long.
• All parentheses in the input string are balanced.
Assumptions:
• The input string always contains balanced parentheses.
• The output string should not contain any parentheses.
• Input: Input: s = "(ab(cd))"
• Explanation: Reverse the substring "cd" to get "dc". Then reverse the entire substring "abdc" to get "dcba". Remove the parentheses to produce the result "dcba".
• Input: Input: s = "a(b(cd)e)f"
• Explanation: Reverse "cd" to get "dc". Then reverse "b(dce)" to get "ecd". Combine with the rest of the string to get "aecdfe".
• Input: Input: s = "a(b)c"
• Explanation: Reverse the substring "b" to get "b". Remove parentheses to produce the result "abc".
Approach: Use a stack-based approach to handle parentheses and efficiently reverse substrings enclosed within them.
Observations:
• Parentheses define a hierarchy of substrings.
• The innermost substrings should be reversed first.
• The string processing can be done iteratively using a stack.
• A stack can track the start positions of parentheses.
• The reverse operation can be performed in-place.
Steps:
• Initialize an empty stack and a string to build the result.
• Iterate through the string, pushing indices of opening parentheses onto the stack.
• When encountering a closing parenthesis, use the top of the stack to determine the substring to reverse.
• Reverse the identified substring and continue processing.
• Remove all parentheses to construct the final string.
Empty Inputs:
• Input: s = ""
• Output: ""
Large Inputs:
• Input: s = "a" + "(" + "b"*999 + ")"
• Output: The reversed result with efficient processing.
Special Values:
• Input: s = "a()b"
• Output: "ab" (Empty parentheses are ignored).
Constraints:
• Ensure processing time is linear relative to the string length.
string reverseParentheses(string s) {
stack<int> stk;
string res;
for(int i = 0; i < s.size(); i++) {
if(s[i] == '(')
stk.push(res.size());
else if(s[i] == ')') {
int j = stk.top();
stk.pop();
reverse(res.begin() + j, res.end());
} else res.push_back(s[i]);
}
return res;
}
1 : Function Declaration
string reverseParentheses(string s) {
Defines the function `reverseParentheses` that takes a string `s` as input.
2 : Stack Initialization
stack<int> stk;
Initializes a stack to store the indices of opening parentheses.
3 : String Initialization
string res;
Initializes the result string to build the final output.
4 : Loop Declaration
for(int i = 0; i < s.size(); i++) {
Iterates through each character in the input string `s`.
5 : Opening Parenthesis Check
if(s[i] == '(')
Checks if the current character is an opening parenthesis.
6 : Push Index
stk.push(res.size());
Pushes the current size of the result string to the stack, marking the start of a substring.
7 : Closing Parenthesis Check
else if(s[i] == ')') {
Checks if the current character is a closing parenthesis.
8 : Top Index Retrieval
int j = stk.top();
Retrieves the index of the matching opening parenthesis from the stack.
9 : Pop Stack
stk.pop();
Removes the top element from the stack as it has been processed.
10 : Reverse Substring
reverse(res.begin() + j, res.end());
Reverses the substring in the result string between the matching parentheses.
11 : Append Character
} else res.push_back(s[i]);
Appends non-parenthesis characters to the result string.
12 : Return Result
return res;
Returns the final modified result string after processing.
Best Case: O(n)
Average Case: O(n)
Worst Case: O(n)
Description: Each character in the string is processed at most twice (once during the initial traversal and once during the reverse operation).
Best Case: O(1) (excluding input and output storage)
Worst Case: O(n)
Description: The stack can grow up to O(n) in the worst case due to nested parentheses.
| LeetCode Solutions Library / DSA Sheets / Course Catalog |
|---|
comments powered by Disqus