Published on

# Reverse In Parentheses

Authors
• Name
Moch Lutfi
@kaptenupi

## 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.

## 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.

test.go
`_37package main_37_37import (_37 "testing"_37)_37_37func solution(s string) string {_37 stack, tmp := make([]byte, 0, len(s)), make([]byte, 0, len(s))_37 for i := range s {_37 if s[i] == ')' {_37 i := len(stack) - 1_37 tmp = tmp[:0]_37 for ; stack[i] != '('; i-- {_37 tmp = append(tmp, stack[i])_37 }_37 stack = append(stack[:i], tmp...)_37 } else {_37 stack = append(stack, s[i])_37 }_37 }_37 return string(stack)_37}_37_37func TestReverseInParentheses(t *testing.T) {_37 tests := []struct {_37 input string_37 want string_37 }{_37 {"(bar)", "rab"},_37 {"foo(bar(baz))blim", "foobazrabblim"},_37 }_37 for _, tt := range tests {_37 if got := solution(tt.input); got != tt.want {_37 t.Errorf("ReverseInParentheses(%v) = %v, want %v", tt.input, got, tt.want)_37 }_37 }_37}`

## Step 2

Iterate string input `s`

test.go
`_37package main_37_37import (_37 "testing"_37)_37_37func solution(s string) string {_37 stack, tmp := make([]byte, 0, len(s)), make([]byte, 0, len(s))_37 for i := range s {_37 if s[i] == ')' {_37 i := len(stack) - 1_37 tmp = tmp[:0]_37 for ; stack[i] != '('; i-- {_37 tmp = append(tmp, stack[i])_37 }_37 stack = append(stack[:i], tmp...)_37 } else {_37 stack = append(stack, s[i])_37 }_37 }_37 return string(stack)_37}_37_37func TestReverseInParentheses(t *testing.T) {_37 tests := []struct {_37 input string_37 want string_37 }{_37 {"(bar)", "rab"},_37 {"foo(bar(baz))blim", "foobazrabblim"},_37 }_37 for _, tt := range tests {_37 if got := solution(tt.input); got != tt.want {_37 t.Errorf("ReverseInParentheses(%v) = %v, want %v", tt.input, got, tt.want)_37 }_37 }_37}`

## 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
test.go
`_37package main_37_37import (_37 "testing"_37)_37_37func solution(s string) string {_37 stack, tmp := make([]byte, 0, len(s)), make([]byte, 0, len(s))_37 for i := range s {_37 if s[i] == ')' {_37 i := len(stack) - 1_37 tmp = tmp[:0]_37 for ; stack[i] != '('; i-- {_37 tmp = append(tmp, stack[i])_37 }_37 stack = append(stack[:i], tmp...)_37 } else {_37 stack = append(stack, s[i])_37 }_37 }_37 return string(stack)_37}_37_37func TestReverseInParentheses(t *testing.T) {_37 tests := []struct {_37 input string_37 want string_37 }{_37 {"(bar)", "rab"},_37 {"foo(bar(baz))blim", "foobazrabblim"},_37 }_37 for _, tt := range tests {_37 if got := solution(tt.input); got != tt.want {_37 t.Errorf("ReverseInParentheses(%v) = %v, want %v", tt.input, got, tt.want)_37 }_37 }_37}`

## 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.
test.go
`_37package main_37_37import (_37 "testing"_37)_37_37func solution(s string) string {_37 stack, tmp := make([]byte, 0, len(s)), make([]byte, 0, len(s))_37 for i := range s {_37 if s[i] == ')' {_37 i := len(stack) - 1_37 tmp = tmp[:0]_37 for ; stack[i] != '('; i-- {_37 tmp = append(tmp, stack[i])_37 }_37 stack = append(stack[:i], tmp...)_37 } else {_37 stack = append(stack, s[i])_37 }_37 }_37 return string(stack)_37}_37_37func TestReverseInParentheses(t *testing.T) {_37 tests := []struct {_37 input string_37 want string_37 }{_37 {"(bar)", "rab"},_37 {"foo(bar(baz))blim", "foobazrabblim"},_37 }_37 for _, tt := range tests {_37 if got := solution(tt.input); got != tt.want {_37 t.Errorf("ReverseInParentheses(%v) = %v, want %v", tt.input, got, tt.want)_37 }_37 }_37}`

## Step 5

• If the current character of the input string `s` is not ')', it is appended to the `stack` slice.
test.go
`_37package main_37_37import (_37 "testing"_37)_37_37func solution(s string) string {_37 stack, tmp := make([]byte, 0, len(s)), make([]byte, 0, len(s))_37 for i := range s {_37 if s[i] == ')' {_37 i := len(stack) - 1_37 tmp = tmp[:0]_37 for ; stack[i] != '('; i-- {_37 tmp = append(tmp, stack[i])_37 }_37 stack = append(stack[:i], tmp...)_37 } else {_37 stack = append(stack, s[i])_37 }_37 }_37 return string(stack)_37}_37_37func TestReverseInParentheses(t *testing.T) {_37 tests := []struct {_37 input string_37 want string_37 }{_37 {"(bar)", "rab"},_37 {"foo(bar(baz))blim", "foobazrabblim"},_37 }_37 for _, tt := range tests {_37 if got := solution(tt.input); got != tt.want {_37 t.Errorf("ReverseInParentheses(%v) = %v, want %v", tt.input, got, tt.want)_37 }_37 }_37}`

## Step 6

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

test.go
`_37package main_37_37import (_37 "testing"_37)_37_37func solution(s string) string {_37 stack, tmp := make([]byte, 0, len(s)), make([]byte, 0, len(s))_37 for i := range s {_37 if s[i] == ')' {_37 i := len(stack) - 1_37 tmp = tmp[:0]_37 for ; stack[i] != '('; i-- {_37 tmp = append(tmp, stack[i])_37 }_37 stack = append(stack[:i], tmp...)_37 } else {_37 stack = append(stack, s[i])_37 }_37 }_37 return string(stack)_37}_37_37func TestReverseInParentheses(t *testing.T) {_37 tests := []struct {_37 input string_37 want string_37 }{_37 {"(bar)", "rab"},_37 {"foo(bar(baz))blim", "foobazrabblim"},_37 }_37 for _, tt := range tests {_37 if got := solution(tt.input); got != tt.want {_37 t.Errorf("ReverseInParentheses(%v) = %v, want %v", tt.input, got, tt.want)_37 }_37 }_37}`

## 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.

## Step 2

Iterate string input `s`

## 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

## 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.

## Step 5

• If the current character of the input string `s` is not ')', it is appended to the `stack` slice.

## Step 6

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

test.go
`_37package main_37_37import (_37 "testing"_37)_37_37func solution(s string) string {_37 stack, tmp := make([]byte, 0, len(s)), make([]byte, 0, len(s))_37 for i := range s {_37 if s[i] == ')' {_37 i := len(stack) - 1_37 tmp = tmp[:0]_37 for ; stack[i] != '('; i-- {_37 tmp = append(tmp, stack[i])_37 }_37 stack = append(stack[:i], tmp...)_37 } else {_37 stack = append(stack, s[i])_37 }_37 }_37 return string(stack)_37}_37_37func TestReverseInParentheses(t *testing.T) {_37 tests := []struct {_37 input string_37 want string_37 }{_37 {"(bar)", "rab"},_37 {"foo(bar(baz))blim", "foobazrabblim"},_37 }_37 for _, tt := range tests {_37 if got := solution(tt.input); got != tt.want {_37 t.Errorf("ReverseInParentheses(%v) = %v, want %v", tt.input, got, tt.want)_37 }_37 }_37}`

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

## 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).

## 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