Blog
Reverse In Parentheses

Reverse In Parentheses

January 12, 2023

Moch Lutfi
Name
Moch Lutfi
Twitter
@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.

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

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)
}
}
}

Step 2

Iterate string input s

test.go

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)
}
}
}

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

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)
}
}
}

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

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)
}
}
}

Step 5

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

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)
}
}
}

Step 6

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

test.go

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)
}
}
}

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

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)
}
}
}

Try it yourself https://go.dev/play/p/sDZq7elgytZ (opens in a new tab)

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
Become the software engineerPalindrome string