Start learning free

LESSON 202 OF 414 · STRINGS

Reverse String in Rust: O(n) with chars().rev() and push

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 4
    Ctrl + Enter to check

    RUST · STRINGS

    Reverse String in Rust, explained

    Problem overview

    The function reverse takes a String called input and returns a new String with the characters in the opposite order. For "hello" the result is "olleh". This version of the lesson asks for O(n) time and O(n) extra space, where n is the length of the string.

    Approach: read backwards, append forwards

    One way to reverse a string is to build the result by putting each character in front of the others. That works, but inserting at the front of a String shifts every byte already stored, so the total work grows as O(n^2).

    The faster way is to flip the roles. Read the input from its last character to its first, and add each character to the end of the result. Adding to the end of a String doesn't move anything that is already there; it takes amortized constant time. A loop of n constant-time appends costs O(n).

    The only difficulty is reading backwards. Rust strings can't be indexed by position, since characters have different byte lengths in UTF-8, so counting an index down from the end is not an option. The character iterator solves this: chars() walks forwards, and rev() turns it around so it walks from the end.

    Step by step

    1. Create the result with room reserved. String::with_capacity(input.len()) makes an empty String whose buffer can already hold as many bytes as the input has. The reversed text uses exactly the same bytes, so the buffer never has to be reallocated while it grows. The variable is mut because it changes, and the lesson names it reversed_string.
    2. Loop over the characters backwards. input.chars().rev() produces the characters from last to first. Name the loop variable c.
    3. Append each character with push(c), which adds one char to the end of the String.
    4. Return reversed_string as the last expression, with no return keyword and no semicolon.

    On "hello" the loop sees o, l, l, e, h in that order, and appending them in turn produces "olleh".

    The solution in Rust

    impl Solution {
    fn reverse(input: String) -> String {
        let mut reversed_string = String::with_capacity(input.len());
        for c in input.chars().rev() {
            reversed_string.push(c);
        }
        reversed_string
    }
}

    Rust details worth knowing:

    • Capacity is measured in bytes. input.len() is the number of bytes, not characters. That is the right quantity here, because reversing characters keeps the total byte count the same. Capacity only avoids reallocations. It doesn't change the contents, and String::new() would give the same result, a little more slowly for long inputs.
    • rev() works on chars(). The iterator can be walked from either end, so Rust can reverse it without first collecting the characters into a vector.
    • Whole characters move. Since chars() yields complete char values, text such as "héllo" becomes "olléh", with the two-byte é intact.
    • push against push_str. push appends one char, and push_str appends a string slice. Here each loop step produces a single char, so push is the right method.
    • The tail expression. The final line has no semicolon, so its value is the function's result.

    The whole body can also be written as one expression, input.chars().rev().collect(), with the return type telling collect to build a String. The loop above is the same idea written out step by step.

    Complexity

    Time: O(n). The loop runs once per character, and each push is amortized constant time. Because the capacity was reserved up front, no reallocation happens at all, though the bound holds without that.

    Space: O(n). The result is a second string as long as the input. The iterator itself uses constant extra space.

    Edge cases and common mistakes

    • Empty string. The loop doesn't run, and the function returns "".
    • One character. "a" gives "a".
    • Palindromes. "racecar" comes back unchanged.
    • Spaces. "ab cd" gives "dc ba", since a space is a character like any other.
    • Forgetting .rev(). Looping over input.chars() and pushing returns an exact copy.
    • Forgetting mut. Without it, push doesn't compile.
    • Sizing by characters. Using input.chars().count() as the capacity would reserve too little for non-ASCII text. Use len(), which counts bytes.

    Testing

    • "hello" gives "olleh".
    • "" gives "".
    • "a" gives "a".
    • "ab cd" gives "dc ba".
    • "héllo" gives "olléh".
    Keep going with RustAbout 340 step-by-step lessons, from your first line of code to coding interviews. Free to start.
    Start learning free