# Reverse In Parentheses

2 min read Tweet this post
Section titled Problem

## Problem

Write a function that reverses characters in (possibly nested) parentheses in the input string.

Input strings will always be well-formed with matching `()`s.

• For `inputString = "(bar)"`, the output should be
`solution(inputString) = "rab"`;

• For `inputString = "koo(bar)baz"`, the output should be
`solution(inputString) = "zoorabbaz"`;

• For `inputString = "koo(bar)baz(blim)"`, the output should be
`solution(inputString) = "zoorabbazmilb"`;

• For `inputString = "koo(bar(baz))blim"`, the output should be
`solution(inputString) = "zoobazrabblim"`.
Because `"koo(bar(baz))blim"` becomes `"koo(barzab)blim"` and then `"zoobazrabblim"`.

• [input] string inputString

A string consisting of lowercase English letters and the characters `(` and `)`. It is guaranteed that all parentheses in `inputString` form a regular bracket sequence.

Guaranteed constraints:
`0 ≤ inputString.length ≤ 50`.

• [output] string

Return `inputString`, with all the characters that were in parentheses reversed.

Section titled Solution

## Solution

Section titled Step%201

## Step 1

Two variables are created, `stack` and `tmp`. `stack` is a slice of bytes with a length of 0, but with a capacity equal to the length of the input string `s`. `tmp` is also a slice of bytes with a length of 0 and capacity equal to the length of the input string.

``````package main

import (
"testing"
)

func solution(s string) string {
stack, tmp := make([]byte, 0, len(s)), make([]byte, 0, len(s))
for i := range s {
if s[i] == ')' {
i := len(stack) - 1
tmp = tmp[:0]
for ; stack[i] != '('; i-- {
tmp = append(tmp, stack[i])
}
stack = append(stack[:i], tmp...)
} else {
stack = append(stack, s[i])
}
}
return string(stack)
}

func TestReverseInParentheses(t *testing.T) {
tests := []struct {
input string
want  string
}{
{"(bar)", "rab"},
{"foo(bar(baz))blim", "foobazrabblim"},
}
for _, tt := range tests {
if got := solution(tt.input); got != tt.want {
t.Errorf("ReverseInParentheses(%v) = %v, want %v", tt.input, got, tt.want)
}
}
}
``````

Section titled Step%202

## Step 2

Iterate string input `s`

Section titled Step%203

## Step 3

• Within the loop, if the current character is `')'`, the code enters another block.
• A variable `i` is created and set to the last index of the `stack` slice.
• Reset `tmp` variable
Section titled Step%204

## Step 4

• A for loop starts, it runs until `stack[i]` is not equal to `'('`, and decrementing the value of `i` in each iteration.
• Within the for loop, each character from the `stack` slice is appended to the `tmp` slice.
• After the for loop, the `stack` slice is updated by replacing the section from `stack[:i]` with the reversed `tmp` slice.
Section titled Step%205

## Step 5

• If the current character of the input string `s` is not ’)’, it is appended to the `stack` slice.
Section titled Step%206

## Step 6

After the for loop completes, the function returns the `stack` slice as a string.

Try it yourself https://go.dev/play/p/sDZq7elgytZ

Section titled Complexity

## Complexity

time complexity: O(n)

space complexity: O(n)

The time complexity is O(n) because the code iterates through the input string once, and for each character, it takes constant time to append it to the stack slice or reverse the characters within the parentheses. Since the number of characters in the input string is n, the time complexity is O(n).

The space complexity is also O(n) because the code creates two slices, stack and tmp, each with a length of n. As the input string can have at most n characters, the space complexity is also O(n).

Section titled Dry%20Run

## Dry Run

Input: `foo(bar(baz))blim`

• foo(barzab)blim
• foobazrabblim
iterationcharstacktmp
0ff
1ofo
2ofoo
3(foo(
4bfoo(b
5afoo(ba
6rfoo(bar
7(foo(bar(
8bfoo(bar(b
9afoo(bar(ba
10zfoo(bar(baz
11)foo(barzabzab
12)foobazrabbazrab
13bfoobazrabbbazrab
14lfoobazrabblbazrab
15ifoobazrabblibazrab
16mfoobazrabblimbazrab
go cp