Reverse In Parentheses

# Reverse In Parentheses

January 12, 2023 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
`package mainimport ( "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 mainimport ( "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 mainimport ( "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 mainimport ( "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 mainimport ( "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 mainimport ( "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
`package mainimport ( "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