String Reversal Approaches in DSA Go

Mental Model

Reversing a string means flipping its characters so the last becomes first and the first becomes last.

Analogy: Imagine reading a sentence backward, starting from the end and moving to the beginning, like rewinding a tape.

Original: H -> e -> l -> l -> o -> null
Reversed: o -> l -> l -> e -> H -> null

Dry Run Walkthrough

Input: string: "hello"

Goal: Reverse the string so it reads "olleh"

Step 1: Start with two pointers: left at 'h' (index 0), right at 'o' (index 4)

h [left] -> e -> l -> l -> o [right] -> null

Why: We need to swap characters from the ends moving inward

Step 2: Swap characters at left and right: 'h' and 'o'

o -> e -> l -> l -> h
[left moves to index 1, right moves to index 3]

Why: Swapping first and last characters reverses their positions

Step 3: Swap characters at left and right: 'e' and 'l'

o -> l -> l -> e -> h
[left moves to index 2, right moves to index 2]

Why: Continue swapping inward until pointers meet

Step 4: Pointers meet at index 2 ('l'), stop swapping

o -> l -> l -> e -> h -> null

Why: All characters reversed, process complete

Result:

o -> l -> l -> e -> h -> null
Reversed string: "olleh"

Annotated Code

DSA Go

package main

import (
	"fmt"
)

func reverseString(s string) string {
	chars := []rune(s) // convert string to rune slice for safe swapping
	left, right := 0, len(chars)-1
	for left < right {
		chars[left], chars[right] = chars[right], chars[left] // swap characters
		left++ // move left pointer right
		right-- // move right pointer left
	}
	return string(chars) // convert back to string
}

func main() {
	input := "hello"
	result := reverseString(input)
	fmt.Println(result)
}

chars := []rune(s) // convert string to rune slice for safe swapping

prepare mutable character array for reversal

left, right := 0, len(chars)-1

initialize pointers at start and end

for left < right {

loop until pointers meet or cross

chars[left], chars[right] = chars[right], chars[left] // swap characters

swap characters at left and right

left++ // move left pointer right

advance left pointer inward

right-- // move right pointer left

advance right pointer inward

return string(chars) // convert back to string

return reversed string

Output

olleh

Complexity Analysis

Time: O(n) because we swap characters from both ends moving inward, touching each character once

Space: O(n) because we create a new slice of runes to hold characters for swapping

vs Alternative: Compared to building a new string by appending characters from the end, this approach swaps in place and is more efficient in memory usage

Edge Cases

empty string

returns empty string immediately without errors

DSA Go

for left < right {

single character string

returns the same single character string as reversal is itself

DSA Go

for left < right {

string with unicode characters

correctly reverses multi-byte characters using rune slice

DSA Go

chars := []rune(s) // convert string to rune slice for safe swapping

When to Use This Pattern

When you need to reverse a string or array in place, use two pointers from both ends moving inward to swap elements efficiently.

Common Mistakes

Mistake: Swapping bytes instead of runes causing broken unicode characters
Fix: Convert string to rune slice before swapping to handle multi-byte characters correctly

Mistake: Using string concatenation in a loop causing O(n²) time
Fix: Use a rune slice and swap in place for O(n) time complexity

Summary

Reverses a string by swapping characters from both ends moving inward.

Use when you need to reverse strings efficiently, including unicode strings.

The key insight is using two pointers to swap characters in place until they meet.

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