Start learning free

LESSON 201 OF 414 · STRINGS

Reverse String in Rust: O(n^2) by Inserting at the Front

Practice O(n2) 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^2) 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". The statement sets the budget for this version of the lesson at O(n^2) time and O(n) extra space, where n is the length of the string.

    Approach: put every new character in front

    Reversing means that the first character ends up last and the last ends up first. A simple way to get there without any index arithmetic is to read the input from left to right and place each character at the front of the result. Watch it grow for "hello":

    • after h: h
    • after e: eh
    • after l: leh
    • after the second l: lleh
    • after o: olleh

    Each character pushes the earlier ones one place to the right, so the first one read finishes at the end.

    Inserting at the front is where the cost comes from. A String stores its text as one block of bytes, so putting something at position 0 means moving every byte already there to make room. The more the result has grown, the more bytes move. Over the whole loop that adds up to about 1 + 2 + ... + n moves, which is O(n^2). The result string grows to the size of the input, which gives the O(n) extra space.

    A faster version reaches O(n) time by appending to the end, which never shifts anything. This lesson shows the simpler, slower idea.

    Step by step

    1. Create the result. Declare a mutable String named reversed with String::new(). It starts empty and grows as characters arrive; mut is needed because it changes.
    2. Loop over the characters. input.chars() yields the characters one at a time, as char values, from the first to the last. Name the loop variable c.
    3. Insert each one at position 0. reversed.insert(0, c) puts c before everything already in reversed, which reverses the order.
    4. Return reversed as the last expression, with no return keyword and no semicolon.

    The solution in Rust

    impl Solution {
    fn reverse(input: String) -> String {
        let mut reversed = String::new();
        for c in input.chars() {
            reversed.insert(0, c);
        }
        reversed
    }
}

    Rust details worth knowing:

    • chars() and not indexing. A Rust string can't be read as input[i]. It holds UTF-8 bytes, where one character takes one to four bytes, so the code walks it with chars(), which decodes one full character at a time.
    • insert takes a byte position. Position 0 is always valid. The method moves the existing bytes and writes the new character, which may take several bytes.
    • Non-ASCII text works. Because the loop moves whole characters, "héllo" becomes "olléh". A byte-by-byte reversal would break the two-byte é and produce invalid text.
    • Ownership. The function takes input by value and builds an independent String. Nothing is borrowed from input in the result.
    • The tail expression. reversed without a semicolon is the function's value. With a semicolon the function would return (), and the compiler would report a type mismatch.

    Complexity

    Time: O(n^2). The loop runs n times. The insert at iteration k shifts the k characters already there, so the total number of moves grows like the sum 1 + 2 + ... + n. Doubling the input roughly quadruples the work.

    Space: O(n). The result holds as many characters as the input. The loop adds only a few variables.

    Edge cases and common mistakes

    • Empty string. The loop doesn't run and the function returns "".
    • One character. "a" gives "a".
    • Spaces and punctuation. They are characters like any other: "ab cd" gives "dc ba".
    • Appending instead of inserting. Using push(c) copies the input unchanged. The reversal comes from putting each character first.
    • Forgetting mut. Without it, reversed.insert(0, c) doesn't compile.
    • Reversing bytes. input.bytes() gives bytes, not characters. For ASCII text the result looks right, but for text such as "héllo" the result is not the reversed text.

    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