Reverse Substrings Between Each Pair of Parentheses
Problem Description
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.
Examples
Input: s = "(abcd)"
Output: "dcba"
Input: s = "(u(love)i)"
Output: "iloveu"
Explanation: The substring "love" is reversed first, then the whole string is reversed.
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 <= 2000
- s only contains lower case English characters and parentheses.
- It is guaranteed that all parentheses are balanced.
The problem statement involves critical thinking rather than just the Brute Force approach. We need to work with our paper and pen to derive observations and then figure out the most optimal approach. Let's figure it out together !!
Optimal Approach
Intuition
Let's take an example and observe how we get to the answer !!
If input s= (u(love)i).
For a moment let's just forget how we can code it. If we do some pen and paper work, we will see the word which is enclosed by a opening and a closing parentheses.
So, we reverse "love" inside (love) → it becomes "elov", resulting in u(elov)i.
Then we reverse the string inside the outer parentheses which is in bold characters of (u(elov)i) → "iloveu". We must also reverse "elov"→ "love" since it lies inside the outer parentheses.
So, the first observation was we will start reversing from the innermost pair and work your way outward.
In naked eye we can see the innermost pair of parentheses. But if we think it programmatically how can we figure out the innermost parentheses ?
Did you observe one thing that in a pair of valid parentheses, when the closing parentheses appears for the first time, we can say we encountered a inner parentheses.
For example:- s= "(u(love)i)"
The first "(" was encountered at 7th index (0-based). And technically it's the innermost.
Similarly,
if s= "(i(learn)(yard)love)".
Here, the first "(" was at 8th index, which means we encountered a inner parentheses, so we have to reverse the word inside the Valid Parentheses i.e. we reverse "learn"→"nrael".
This was not the only pair of innermost parentheses because at index 14, we encounter another ")", which means the string "yard" need to be reversed again which will result in (inraeldraylove).
Then we reverse the whole word inside the only pair of parentheses which is in bold characters of (inraeldraylove).
Then finally our answer became, evolyardlearni.
We can say that the order of reversing doesn’t matter because once the innermost substring is reversed, it becomes a normal string without parentheses. By the time you reverse the outer substring, all inner substrings are already processed correctly.
But it's not enough for our logic, how can we simulate this process to get the result?
Fine, we traversed the string from left to right. Whenever, we got a ")", we reversed the string present inside it. So, we have to store the previously encountered string somewhere in order to reverse it.
But, it is hectic because storing every such substrings requires a lot of space.
For example:- s= "(u(love)i)"
the first pair of parentheses is (love).
If , we get to know the index of the opening and closing parentheses, can we figure out which part of the string is to be reversed ?
Yes, once we get the starting index and ending index of a string, we can get the substring and then reverse it !!
But where to store the indices ?
We will use a stack to store the indices for this purpose. Whenever we encounter a "(" we will push the index of it on the stack. When we encounter a ")", we will pop the top element of the stack because the top of the stack will contain the "(" which was encountered the latest. This way we will get the indices of the innermost pair of parentheses.
Once, we get the indices we will extract the substring and then reverse it. How to code it ip?
Approach
Initialization: Use a stack to keep track of the indices where each opening parenthesis '(' is encountered.
Use a string to build the resulting string as we process the input.
Iterate through the string:Opening parenthesis '(': Push the current length of the string to the stack. This marks the starting index of the substring that may need to be reversed.Closing parenthesis ')': Pop the last index from the stack to get the corresponding opening parenthesis. Call the reverse function to reverse the substring between this index and the current length of the string minus one.Other characters: Append them directly to the StringBuilder.
Reversal Function: Reverse the characters in the string between the given start and end indices.
Return: The final processed string from the string.
Let us understand this with a video,
Dry-Run
Input
s= "(evol(yard)(learn)i)"
Output
"ilearnyardlove"
Initial Setup:
- Input string: "(evol(yard)(learn)i)"
- Stack: []
- Result: ""
Iteration by Iteration Breakdown:
Character (:
- Stack: [0]
- Result: ""
Character e:
- Stack: [0]
- Result: "e"
Character v:
- Stack: [0]
- Result: "ev"
Character o:
- Stack: [0]
- Result: "evo"
Character l:
- Stack: [0]
- Result: "evol"
Character (:
- Stack: [0, 4]
- Result: "evol"
Character y:
- Stack: [0, 4]
- Result: "evoly"
Character a:
- Stack: [0, 4]
- Result: "evolya"
Character r:
- Stack: [0, 4]
- Result: "evolyar"
Character d:
- Stack: [0, 4]
- Result: "evolyard"
Character ):
- Stack: [0]
- Reverse substring from index 4 to 9: "yard" → "dray"
- Result after reversal: "evoldray"
Character (:
- Stack: [0, 8]
- Result: "evoldray"
Character l:
- Stack: [0, 8]
- Result: "evoldrayl"
Character e:
- Stack: [0, 8]
- Result: "evoldrayle"
Character a:
- Stack: [0, 8]
- Result: "evoldraylea"
Character r:
- Stack: [0, 8]
- Result: "evoldraylear"
Character n:
- Stack: [0, 8]
- Result: "evoldraylearn"
Character ):
- Stack: [0]
- Reverse substring from index 8 to 13: "learn" → "nrael"
- Result after reversal: "evoldraynrael"
Character i:
- Stack: [0]
- Result: "evoldraynraeli"
Character ):
- Stack: []
- Reverse substring from index 0 to 14: "evoldraynraeli" → "ilearnyardlove"
- Result after reversal: "ilearnyardlove"
Final Output: Result: "ilearnyardlove"
Optimal Code in all Languages.
1. C++ Try on Compiler
// Function to reverse substrings enclosed in parentheses
string reverseParentheses(string s) {
// Stack to store indices of '('
stack<int> stack;
// String to construct the result
string result;
// Iterate over each character in the string
for (char currentChar : s) {
// If current character is '(', push the current length of result onto stack
if (currentChar == '(')
stack.push(result.length());
// If current character is ')', reverse the substring
else if (currentChar == ')') {
int start = stack.top();
stack.pop();
reverse(result, start, result.length() - 1);
}
// If current character is a letter, append it to result
else result += currentChar;
}
// Return the final processed string
return result;
}
// Function to reverse a substring in a string
void reverse(string &s, int start, int end) {
while (start < end) {
// Swap characters at 'start' and 'end'
swap(s[start], s[end]);
start++;
end--;
}
}2. Java Try on Compiler
class Solution {
// Method to reverse a substring in StringBuilder
public void reverse(StringBuilder sb, int start, int end) {
while (start < end) {
// Swap characters at 'start' and 'end'
char temp = sb.charAt(start);
sb.setCharAt(start, sb.charAt(end));
start++;
sb.setCharAt(end, temp);
end--;
}
}
// Method to reverse substrings enclosed in parentheses
public String reverseParentheses(String s) {
// Stack to store indices of '('
Stack<Integer> stack = new Stack<>();
// StringBuilder to construct the result
StringBuilder result = new StringBuilder();
// Iterate over each character in the string
for (char currentChar : s.toCharArray()) {
// If current character is '(', push the current length of result onto stack
if (currentChar == '(')
stack.push(result.length());
// If current character is ')', reverse the substring
else if (currentChar == ')') {
int start = stack.pop();
reverse(result, start, result.length() - 1);
}
// If current character is a letter, append it to result
else result.append(currentChar);
}
// Return the final processed string
return result.toString();
}
}
3. Python Try on Compiler
# Function to reverse a substring in a list
def reverse(sb, start, end):
while start < end:
# Swap elements at 'start' and 'end'
sb[start], sb[end] = sb[end], sb[start]
start += 1
end -= 1
# Function to reverse substrings enclosed in parentheses
def reverseParentheses(s):
# Stack to store indices of '('
stack = []
# List to construct the result as strings are immutable in Python
result = []
# Iterate over each character in the string
for currentChar in s:
# If current character is '(', push the current length of result onto stack
if currentChar == '(':
stack.append(len(result))
# If current character is ')', reverse the substring
elif currentChar == ')':
start = stack.pop()
reverse(result, start, len(result) - 1)
# If current character is a letter, append it to result
else:
result.append(currentChar)
# Return the final processed string by joining the list
return ''.join(result)4. JavaScript Try on Compiler
// Function to reverse a substring in an array
function reverse(arr, start, end) {
while (start < end) {
let temp = arr[start];
arr[start] = arr[end];
arr[end] = temp;
start++;
end--;
}
}
// Function to reverse substrings enclosed in parentheses
function reverseParentheses(s) {
let stack = [];
let result = [];
for (let currentChar of s) {
if (currentChar === '(') {
stack.push(result.length);
} else if (currentChar === ')') {
let start = stack.pop();
reverse(result, start, result.length - 1);
} else {
result.push(currentChar);
}
}
return result.join('');
}
Time Complexity: O(n)
Loop through the string: The algorithm iterates through the string once, processing each character individually. This loop runs in O(n), where n is the length of the input string.
Stack Operations: The stack operations (push and pop) are used for handling parentheses, and they each take O(1) time. Since each parenthesis is processed exactly once (either pushed onto the stack when encountered or popped when a closing parenthesis is encountered), the total time spent on stack operations is also O(n).
Reversing the Substring: When a closing parenthesis is encountered, the substring between the matching parentheses is reversed. The reversal operation in the reverse() function works in O(k) time, where k is the length of the substring being reversed.
However, the total number of characters in all reversals is bounded by the length of the string n, meaning that across all reversals, the total time spent on reversing substrings is O(n).
Thus, the total time complexity is: O(n)+O(n)=O(n)
Space Complexity: O(n)
Auxiliary Space Complexity refers to the extra space required by an algorithm other than the input space.
StringBuilder (result): The StringBuilder result is used to build the final output string. In the worst case, every character of the input string is stored in the result, so this requires O(n) auxiliary space.
Stack: The stack is used to track the positions of the opening parentheses. In the worst case, if every character is an opening parenthesis (e.g., (((...)))), the stack will store all the indices, and thus it will require O(n) space.
Temporary Variables: The reverse() function uses a few temporary variables (such as temp for swapping characters). These take constant space, so they do not contribute significantly to auxiliary space complexity.
Thus, the total auxiliary space complexity is: O(n)
Total Space Complexity The total space complexity is the sum of:
- Input string s of length n: O(n)
- Auxiliary space: O(n)
Thus, the total space complexity is: O(n)
Learning Tip
A string is a valid parentheses string (denoted VPS) if and only if it consists of "(" and ")" characters only, and:
- It is the empty string, or
- It can be written as AB (A concatenated with B), where A and B are VPS's, or
- It can be written as (A), where A is a VPS.
We can similarly define the nesting depth depth(S) of any VPS S as follows:
- depth("") = 0
- depth(A + B) = max(depth(A), depth(B)), where A and B are VPS's
- depth("(" + A + ")") = 1 + depth(A), where A is a VPS.
For example, "", "()()", and "()(()())" are VPS's (with nesting depths 0, 1, and 2), and ")(" and "(()" are not VPS's.
Given a VPS seq, split it into two disjoint subsequences A and B, such that A and B are VPS's (and A.length + B.length = seq.length).
Now choose any such A and B such that max(depth(A), depth(B)) is the minimum possible value.
Return an answer array (of length seq.length) that encodes such a choice of A and B: answer[i] = 0 if seq[i] is part of A, else answer[i] = 1. Note that even though multiple answers may exist, you may return any of them.
A parentheses string is a non-empty string consisting only of '(' and ')'. It is valid if any of the following conditions is true:
- It is ().
- It can be written as AB (A concatenated with B), where A and B are valid parentheses strings.
- It can be written as (A), where A is a valid parentheses string.
You are given a parentheses string s and a string locked, both of length n. locked is a binary string consisting only of '0's and '1's. For each index i of locked,
- If locked[i] is '1', you cannot change s[i].
- But if locked[i] is '0', you can change s[i] to either '(' or ')'.
Return true if you can make s a valid parentheses string. Otherwise, return false.