String Reversal Approaches in DSA Go - Execution Trace

Concept Flow - String Reversal Approaches

Start with original string

↓

Choose reversal method

↓

Method 1: Two-pointer swap

↓

Swap characters from ends moving inward

↓

Complete when pointers meet or cross

↓

Method 2: Build new reversed string

↓

Iterate from end to start

↓

Append characters to new string

↓

Return new reversed string

↓

Output reversed string

↓

End

The flow starts with the original string, then chooses a reversal method: either swapping characters in place using two pointers or building a new reversed string by iterating from the end. Finally, the reversed string is output.

Execution Sample

DSA Go

func reverseTwoPointer(s string) string {
    chars := []rune(s)
    left, right := 0, len(chars)-1
    for left < right {
        chars[left], chars[right] = chars[right], chars[left]
        left++
        right--
    }
    return string(chars)
}

This code reverses a string by swapping characters from the ends moving inward using two pointers.

Execution Table

Step	Operation	left pointer	right pointer	Characters Array	Action
1	Initialize pointers	0	4	[h e l l o]	Set left=0, right=4
2	Check condition left < right	0	4	[h e l l o]	0 < 4 is True, proceed
3	Swap chars[left] and chars[right]	0	4	[o e l l h]	Swap 'h' and 'o'
4	Increment left, decrement right	1	3	[o e l l h]	left=1, right=3
5	Check condition left < right	1	3	[o e l l h]	1 < 3 is True, proceed
6	Swap chars[left] and chars[right]	1	3	[o l l e h]	Swap 'e' and 'l'
7	Increment left, decrement right	2	2	[o l l e h]	left=2, right=2
8	Check condition left < right	2	2	[o l l e h]	2 < 2 is False, stop loop
9	Return reversed string	-	-	[o l l e h]	Return "olleh"

💡 Loop ends when left pointer is no longer less than right pointer (left=2, right=2), meaning all swaps done.

Variable Tracker

Variable	Start	After Step 3	After Step 6	After Step 7	Final
left	0	0	1	2	2
right	4	4	3	2	2
chars	[h e l l o]	[o e l l h]	[o l l e h]	[o l l e h]	[o l l e h]

Key Moments - 3 Insights

Why do we stop swapping when left equals right?

Because when left equals right, it means we reached the middle character in an odd-length string, which does not need swapping. See execution_table step 8 where condition left < right becomes false.

Why do we convert string to a rune slice before swapping?

Strings are immutable in Go, so we convert to a rune slice to swap characters in place. This is shown in execution_sample code line 2 and tracked in variable_tracker for chars.

What happens if the string is empty or has one character?

The loop condition left < right will be false immediately, so no swaps occur and the original string is returned as is.

Visual Quiz - 3 Questions

Look at the execution_table at step 6, what is the state of the chars array?

A [h e l l o]

B [o l l e h]

C [o e l l h]

D [o l l l h]

💡 Hint

Refer to the 'Characters Array' column at step 6 in execution_table.

At which step does the loop condition become false?

A Step 7

B Step 9

C Step 8

D Step 6

💡 Hint

Check the 'Action' column for condition checks in execution_table.

If the input string was "abc", what would be the final chars array after reversal?

A [c b a]

B [a b c]

C [c a b]

D [b a c]

💡 Hint

Think about swapping first and last characters as shown in execution_table steps.

Concept Snapshot

String Reversal Approaches in Go:
- Convert string to rune slice for mutability
- Use two-pointer method: swap chars[left] and chars[right]
- Move pointers inward until they meet or cross
- Return string from modified rune slice
- Alternative: build new string from end to start

Full Transcript

This visual execution trace shows how to reverse a string in Go using the two-pointer swap method. We start with the original string converted to a rune slice for mutability. Two pointers, left and right, start at the beginning and end of the slice. We swap the characters at these pointers and then move the pointers inward. This continues until the pointers meet or cross, meaning the string is fully reversed. The final reversed string is returned. Key points include stopping the loop when left is no longer less than right and why we use a rune slice instead of a string for swapping. The execution table tracks each step, pointer positions, and the state of the character array. The variable tracker shows how pointers and the array change after swaps. The quiz questions test understanding of the array state at specific steps and loop termination conditions.

Practice

1. What does the strings.Reverse function do in Go if it existed? (Assume it reverses the string.)

easy

A. It converts the string to uppercase.

B. It returns the input string with characters in reverse order.

C. It removes all vowels from the string.

D. It splits the string into words.

Solution

1. Step 1: Understand the function name and purpose

   The function name Reverse suggests it changes the order of characters.

2. Step 2: Interpret the expected behavior

   Reversing a string means the last character becomes first, and so on.

3. Final Answer:

   It returns the input string with characters in reverse order. -> Option B

4. Quick Check:

   Reverse means flip order [OK]

Hint: Reverse means flip the order of characters [OK]

Common Mistakes:

• Confusing reverse with uppercase conversion
• Thinking reverse removes characters
• Assuming reverse splits words

2. Which of the following Go code snippets correctly reverses a string s?

easy

A. var reversed string
for i := len(s)-1; i >= 0; i-- {
reversed += string(s[i])
}

B. for i := 0; i < len(s); i++ {
reversed += string(s[i])
}

C. reversed := strings.ToUpper(s)

D. reversed := strings.Split(s, " ")

Solution

1. Step 1: Analyze the loop direction

   var reversed string for i := len(s)-1; i >= 0; i-- { reversed += string(s[i]) } loops from the last character to the first, building reversed string.

2. Step 2: Check other options

   for i := 0; i < len(s); i++ { reversed += string(s[i]) } loops forward, so no reversal. reversed := strings.ToUpper(s) changes case, reversed := strings.Split(s, " ") splits words.

3. Final Answer:

   Option A correctly reverses the string. -> Option A

4. Quick Check:

   Loop backward to reverse [OK]

Hint: Loop backward from end to start to reverse [OK]

Common Mistakes:

• Looping forward instead of backward
• Using string functions that don't reverse
• Confusing splitting with reversing

3. What is the output of this Go code?

func main() {
  s := "hello"
  reversed := ""
  for i := len(s) - 1; i >= 0; i-- {
    reversed += string(s[i])
  }
  fmt.Println(reversed)
}

medium

A. olleh

B. hello

C. h

D. error

Solution

1. Step 1: Trace the loop from end to start

   The loop starts at index 4 ('o') and goes to 0 ('h'), appending characters in reverse order.

2. Step 2: Build the reversed string

   Characters appended: 'o', 'l', 'l', 'e', 'h' forming "olleh".

3. Final Answer:

   olleh -> Option A

4. Quick Check:

   Reverse of "hello" is "olleh" [OK]

Hint: Reverse string by appending chars from end to start [OK]

Common Mistakes:

• Reading string forward instead of backward
• Printing original string by mistake
• Expecting error due to string indexing

4. Find the error in this Go code that tries to reverse a string s:

func reverse(s string) string {
  var reversed string
  for i := 0; i <= len(s); i++ {
    reversed += string(s[len(s)-i])
  }
  return reversed
}

medium

A. The function should return reversed as a byte slice.

B. The string concatenation should use +=.

C. The loop condition should be i < len(s), not <=.

D. The loop should start from len(s) and go down to 0.

Solution

1. Step 1: Check loop bounds

   The loop runs from 0 to len(s) inclusive, but string indices go from 0 to len(s)-1.

2. Step 2: Identify out-of-range index

   Accessing s[len(s)-i] when i=0 is s[len(s)], which is out of range and causes runtime error.

3. Final Answer:

   The loop condition should be i < len(s), not <=. -> Option C

4. Quick Check:

   Index must be within 0 to len(s)-1 [OK]

Hint: Loop index must stay inside string length bounds [OK]

Common Mistakes:

• Using <= instead of < in loop condition
• Accessing index len(s) which is invalid
• Confusing string and byte slice types

5. Given a string with Unicode characters like "Go语言", which approach correctly reverses it preserving characters properly in Go?

hard

A. Split string by spaces and reverse the words.

B. Use a byte slice and reverse bytes directly.

C. Use strings.ToUpper and then reverse.

D. Convert string to []rune, reverse the rune slice, then convert back to string.

Solution

1. Step 1: Understand Unicode in Go strings

   Go strings are byte sequences; Unicode characters may be multiple bytes.

2. Step 2: Use rune slice to handle Unicode characters

   Converting to []rune treats each Unicode character as one element, safe to reverse.

3. Step 3: Reverse rune slice and convert back

   Reversing []rune reverses characters correctly, then convert back to string.

4. Final Answer:

   Convert string to []rune, reverse runes, then back to string. -> Option D

5. Quick Check:

   Use runes for Unicode-safe reversal [OK]

Hint: Use []rune to reverse Unicode strings safely [OK]

Common Mistakes:

• Reversing bytes breaks Unicode characters
• Using uppercase conversion instead of reversing
• Reversing words instead of characters