Published on

Reverse In Parentheses

Authors

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.

Solution

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

_37
package main
_37
_37
import (
_37
"testing"
_37
)
_37
_37
func 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
_37
func 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

_37
package main
_37
_37
import (
_37
"testing"
_37
)
_37
_37
func 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
_37
func 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

_37
package main
_37
_37
import (
_37
"testing"
_37
)
_37
_37
func 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
_37
func 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

_37
package main
_37
_37
import (
_37
"testing"
_37
)
_37
_37
func 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
_37
func 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

_37
package main
_37
_37
import (
_37
"testing"
_37
)
_37
_37
func 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
_37
func 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

_37
package main
_37
_37
import (
_37
"testing"
_37
)
_37
_37
func 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
_37
func 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
ExpandClose

_37
package main
_37
_37
import (
_37
"testing"
_37
)
_37
_37
func 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
_37
func 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