Problem overview
The method ReverseParentheses receives a string s of lowercase letters and balanced parentheses. It must reverse the text inside every pair of matching parentheses, starting with the innermost pair, and return the result without any parentheses.
The examples show how nesting matters:
"(abcd)"becomes"dcba"."(u(love)i)"becomes"iloveu". Firstloveturns intoevol, which makes the whole textuevoli. Then the outer pair reverses that text intoiloveu."(yme(oc(da))gla)"becomes"algocademy". The reversals happen in the orderdatoad, thenocadtodaco, and finally the whole text toalgocademy.
Approach: one buffer per open parenthesis
Reversing from the inside out matches the way a stack behaves: the most recently opened parenthesis is the first to close. So we keep a stack of buffers, which are strings under construction, one for each level of nesting.
- Start with one empty buffer. It collects the characters that appear outside every pair of parentheses.
- On
(, add a new empty buffer. Everything up to the matching)goes into it. - On
), take the top buffer off the stack and reverse it. That text now belongs to the buffer below, which is the level that contained the parentheses, so append it there. - On any other character, append it to the top buffer.
Take "(u(love)i)". After the first (, the buffers are ["", ""]. The letter u goes into the top one. The second ( adds a third buffer, and love fills it, giving ["", "u", "love"]. The first ) removes love, reverses it into evol, and appends it to u, so the buffers are ["", "uevol"]. The letter i makes it "uevoli". The last ) reverses that into iloveu and appends it to the bottom buffer. One buffer is left, and it holds the answer.
Every pair that encloses a character reverses it once, so a letter inside two pairs is reversed twice and ends up in its original order. The stack of buffers handles that without any special counting.
Step by step
- Create the stack of buffers. A
List<string>namedresis used as the stack, and its last element is the top. A collection initializer,{ "" }, starts it with one empty string. - Loop over the characters of
swithforeach, using acharvariablec. - Open a level. When
c == '(', add an empty string tores. - Close a level. The
else ifbranch handlesc == ')'. - Take the top buffer off. Copy
res[res.Count - 1]intotop, then callRemoveAt(res.Count - 1).RemoveAtreturns nothing, so the copy has to come first. - Reverse it. Build
reversedTopfromtop.Reverse().ToArray(). - Append it to the level beneath. After the removal, the last element is the enclosing buffer, and
+=adds the reversed text to it. - Handle ordinary characters. In the
elsebranch, appendcto the last buffer. - Return the joined result. For balanced input only one buffer remains, and
string.Concat(res)joins whatever is in the list.
The solution in C#
class Solution {
public string ReverseParentheses(string s) {
List<string> res = new List<string> { "" };
foreach (char c in s) {
if (c == '(') {
res.Add("");
} else if (c == ')') {
string top = res[res.Count - 1];
res.RemoveAt(res.Count - 1);
string reversedTop = new string(top.Reverse().ToArray());
res[res.Count - 1] += reversedTop;
} else {
res[res.Count - 1] += c;
}
}
return string.Concat(res);
}
}
Some C# details to notice:
- A list as a stack.
res.Add(...)pushes at the end,res[res.Count - 1]reads the top, andRemoveAt(res.Count - 1)pops it. A list is used instead ofStack<string>because the top element has to be modified in place with+=, and a list lets you assign to an index. - Reversing a string. A
stringhas noReversemethod of its own.top.Reverse()is a LINQ method that treats the string as a sequence of characters and yields them backwards.ToArray()collects them into achar[], andnew string(...)turns that array back into a string. Another way istop.ToCharArray()followed byArray.Reverseon the array. - Immutable strings. A C# string never changes after it is created.
res[i] += xbuilds a new string and stores it in that slot of the list. - Appending a
char. When one side of+is a string, acharon the other side is appended as a character, so"ab" + 'c'is"abc". Between twocharvalues,+adds their numeric codes instead:'a' + 'b'is the integer 195. - Quotes. Single quotes make a
char, as in'('. Double quotes make a string, as in"". string.Concat(res)joins all the strings of a list into one string without a separator.
Complexity
Time: O(n²) in the worst case. The loop visits each character once, but a closing parenthesis reverses and appends a whole buffer, and strings are copied on every +=. In deeply nested input, the same letters are copied again at every level. With the lesson's limit of 2,000 characters, this is fast. A linear-time solution exists that precomputes the matching pairs and jumps between them, but the stack of buffers is simpler to write and reason about.
Space: O(n). The buffers together never hold more than the characters of the input, apart from the temporary copies made during a reversal.
Edge cases and common mistakes
- No parentheses. For
"abc"the single buffer collects all three letters, and the answer is"abc". - Text around a pair. For
"a(bc)d"the answer is"acbd". Only the part inside the parentheses is reversed. - An empty pair. For
"()"the buffer is empty, and reversing nothing leaves nothing. - Reading the top after the removal. The buffer to append to is the one beneath the removed one, so the index
res.Count - 1must be evaluated afterRemoveAt. The code does this, and the order of those lines matters. - Forgetting to capture the removed value.
RemoveAtreturnsvoid, so the top buffer has to be copied intotopbefore it is removed. - Reversing in the wrong order. Reversing the whole string first and then undoing pairs gets confusing quickly. The stack processes the innermost pair first by construction.
- Leaving the parentheses in. They never get appended to any buffer, so the result contains letters only.
Testing
"(abcd)"gives"dcba"."(u(love)i)"gives"iloveu"."(yme(oc(da))gla)"gives"algocademy"."a(bc)d"gives"acbd"."abc"gives"abc".