Reverse In Parentheses

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.

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

Iterate string input s

• 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

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

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

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

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

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

Input: foo(bar(baz))blim

• foo(barzab)blim
• foobazrabblim