Start learning free

LESSON 171 OF 348 · STRINGS

Reverse String in TypeScript: O(n²) by Prepending

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

    TYPESCRIPT · STRINGS

    Reverse String in TypeScript, explained

    Problem overview

    The method reverse of class Solution receives a string, input, and returns the same characters in the opposite order. The statement asks you to do it without built-in helpers such as the array reverse method, so you build the result yourself, one character at a time.

    In the example, "hello" becomes "olleh". The first character of the input becomes the last of the output, the second becomes the second to last, and so on.

    This version is allowed O(n²) time and O(n) extra space. That is a generous budget, and it tells you the simple idea is welcome here: you don't need a clever trick.

    Approach: put each new character in front

    Start with an empty result and read the input from left to right. Each character you read goes to the front of the result, not the back. After reading h the result is h. After e it is eh. After l it is leh, and so on, until the whole string has been read in reverse.

    read h  -> h
read e  -> eh
read l  -> leh
read l  -> lleh
read o  -> olleh

    Strings in TypeScript are immutable, so "putting a character in front" means building a brand new string from the character plus the old result. If each such step copies the old result, the first step copies 0 characters, the second 1, the third 2, and so on. Adding those up gives about n²/2 copied characters, which is the O(n²) in the statement. The extra space is the result string, which holds n characters, so it is O(n).

    The lesson's other versions of this problem build the result by appending instead. That avoids the repeated copying on paper and reaches O(n). This lesson keeps the prepending idea because it is the shortest to write and the easiest to see working.

    Step by step

    1. Create the result. Declare reversedString with let, since it changes on every pass, and start it as an empty string.
    2. Visit every character. A for...of loop over input hands you one character per pass, from first to last. The loop variable character is declared with const, which is fine here: each pass gets a fresh binding, and you never reassign it inside the loop.
    3. Prepend. Assign character + reversedString back to reversedString. Writing the new character on the left puts it in front of everything read so far.
    4. Return the result after the loop has finished.

    The solution in TypeScript

    class Solution {
    reverse(input: string): string {
        let reversedString = "";
        for (const character of input) {
            reversedString = character + reversedString;
        }
        return reversedString;
    }
}

    The TypeScript details worth a closer look:

    • Inferred type. let reversedString = "" has no annotation, yet its type is string, inferred from the initial value. Annotations are erased when the code is compiled to JavaScript, so they never change what the program does.
    • for...of versus for...in. for...of walks the characters of a string. for...in would give you the indexes as strings, which is not what you want here.
    • const in a loop. const character looks like it would fail on the second pass, but each pass creates a new variable, so nothing is reassigned.
    • Whole characters. for...of steps through a string by whole characters, so a character made of two 16-bit units, such as an emoji, stays in one piece. reverse("a😀b") gives "b😀a". An index loop over input[i] would split such a character in two.
    • Class method. reverse doesn't use this, but it still lives in the class. You call it on an instance: new Solution().reverse("hello").

    Complexity

    Time: O(n²). The loop runs n times. In the lesson's cost model, every prepend builds a new string by copying the previous result, so pass k costs about k character copies. The total is 1 + 2 + … + n, about n²/2. JavaScript engines often store the pieces of a concatenation cleverly and can do better than this in practice, but the analysis assumes the copy, and it is the safe way to reason about code that works on any engine.

    Space: O(n). The result holds n characters. Older intermediate strings can be thrown away as the loop moves on, so there is no extra growth beyond a constant number of strings of at most that length.

    Edge cases and common mistakes

    • Empty string. The loop doesn't run, and the function returns "".
    • One character. "a" comes back as "a".
    • Palindromes. "racecar" reverses to itself, which is a handy test.
    • Appending instead of prepending. reversedString + character rebuilds the original string unchanged. The order of the two operands is the whole idea.
    • Forgetting to return. A method declared with return type string that never returns one gets a compiler error saying a function whose declared type is not void must return a value.
    • Using const for the result. reversedString is reassigned in every pass, so it needs let.

    Testing

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