Start learning free

LESSON 224 OF 338 · TWO POINTERS

Reverse String in Go: Two Pointers on a Byte Slice

Practice O(n) Read the full explanation

Given a string, write a function that reverses that string without using built-in functions or libraries.

Example:

Input:  "hello"

Output: "olleh"

Note:

Your algorithm should run in O(n) time and use O(n) extra space.


STEP 1 OF 9
    Ctrl + Enter to check

    GO · TWO POINTERS

    Reverse String in Go, explained

    Problem overview

    The function reverseString receives a string, input, and returns a new string with the characters in the opposite order, without library helpers. For "hello" the result is "olleh". The statement allows O(n) time and O(n) extra space.

    Approach: swap pairs from the ends

    Reversing means that the first character trades places with the last, the second with the second-to-last, and so on until the middle. Two pointers do this: left starts at the first position, right at the last, and each step swaps the two elements and moves the pointers toward each other. When left < right is no longer true, every pair has been swapped. For an odd length, the middle element has no partner and stays in place.

    There is one Go-specific obstacle: strings are immutable. You can't write input[0] = 'x'; the compiler rejects it. So the function first copies the string into a mutable byte slice, reverses the slice, and converts it back. That copy is the O(n) extra space the statement allows.

    Tracing "hello"

    After the copy, chars holds the bytes of h e l l o, with left = 0 and right = 4. The first pass swaps h and o, giving o e l l h, and the pointers become 1 and 3. The second pass swaps e and l, giving o l l e h, and the pointers become 2 and 2. Now left < right is false, so the loop ends. The middle l never moved, and the function returns "olleh".

    Step by step

    1. Copy the string into a slice. chars := []byte(input) allocates a new slice with the string's bytes, which can be changed freely.
    2. Create left starting at 0.
    3. Create right starting at len(chars) - 1, the last index.
    4. Loop while left < right with a condition-only for, Go's replacement for while.
    5. Call swapBytes(chars, left, right) inside the loop to exchange the two elements.
    6. Declare the helper swapBytes, taking the slice and two indices. Because a slice shares its backing array with the caller, changes made inside the helper are visible in reverseString.
    7. Swap through a temporary. Save chars[i] in temp, copy chars[j] into chars[i], then put temp into chars[j]. Without the temporary, the first assignment would overwrite a value that is still needed.
    8. Move the pointers with left++ and right--.
    9. Convert back with string(chars) and return it.

    The solution in Go

    func reverseString(input string) string {
    chars := []byte(input)
    left := 0
    right := len(chars) - 1
    for left < right {
        swapBytes(chars, left, right)
        left++
        right--
    }
    return string(chars)
}

func swapBytes(chars []byte, i, j int) {
    temp := chars[i]
    chars[i] = chars[j]
    chars[j] = temp
}

    The Go details worth a closer look:

    • Conversions copy. []byte(input) and string(chars) each make a new copy. The original input is never modified: after t := reverseString(s) with s = "hello", s still prints hello and t prints olleh.
    • Slices share memory. A slice is a small header pointing at an array. Passing chars to swapBytes copies the header, not the bytes, so both functions see the same elements. That is why the helper needs no return value. Assigning one slice to another variable shares the data the same way: after c := b and c[0] = 'z', the slice b shows the change too.
    • Grouped parameters. i, j int declares two parameters of the same type.
    • Tuple assignment. Go can swap without a temporary: chars[i], chars[j] = chars[j], chars[i]. The lesson's version spells out each move.
    • Bytes, not characters. This solution reverses bytes. For ASCII text that is the same as reversing characters. A character outside ASCII takes several bytes in UTF-8, and reversing the bytes breaks it: reverseString("héllo") returns an invalid string. To handle such text, convert to []rune instead, which holds one element per character, and swap those; that gives olléh.

    Reversing text that isn't ASCII

    If the input can contain accented letters, reverse runes instead of bytes. A rune is one Unicode character, and the swap can use Go's tuple assignment:

    r := []rune("héllo")
for i, j := 0, len(r)-1; i < j; i, j = i+1, j-1 {
    r[i], r[j] = r[j], r[i]
}
fmt.Println(string(r)) // olléh

    The loop is the same two-pointer idea; only the element type changed. This is a side note, since the lesson's tests use plain text.

    Complexity

    Time: O(n). The copy, the loop (at most n / 2 swaps) and the final conversion are each linear.

    Space: O(n). The byte slice and the result string are new copies of the input. The swapping itself happens in place.

    Edge cases and common mistakes

    • Empty string. right is -1, the loop is skipped, and the function returns "".
    • One character. "a" comes back unchanged.
    • Even and odd lengths. "abcd" gives "dcba" after two swaps. The loop condition left < right stops correctly in both cases.
    • Trying to modify the string. Assigning to an element of a string doesn't compile, so the slice copy is required.
    • Using left <= right. For odd lengths this swaps the middle element with itself. It is harmless but pointless.
    • Swapping without a temporary. Writing chars[i] = chars[j] followed by chars[j] = chars[i] leaves both positions with the same value.
    • Forgetting to move the pointers. The loop swaps the same pair back and forth forever.

    Testing

    • "hello" gives "olleh".
    • "" gives "".
    • "a" gives "a".
    • "abcd" gives "dcba".
    Keep going with GoAbout 340 step-by-step lessons, from your first line of code to coding interviews. Free to start.
    Start learning free