Start learning free

LESSON 172 OF 348 · STRINGS

Reverse String in TypeScript: O(n) with a Reverse Index Loop

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

    TYPESCRIPT · STRINGS

    Reverse String in TypeScript, explained

    Problem overview

    The method reverse of class Solution takes a string, input, and returns its characters in the opposite order, without using built-in helpers such as the array reverse method. For "hello" the answer is "olleh".

    This version asks for O(n) time and O(n) extra space, so the work has to grow in step with the length of the string and not faster.

    Approach: walk the string backwards and append

    Instead of reading the input from the left and inserting each character at the front, read it from the right and add each character at the back. The first character you meet is the last one of the input, and it should come first in the output. Appending it to an empty result puts it there. The next character from the right goes after it, and so on.

    read o (index 4) -> o
read l (index 3) -> ol
read l (index 2) -> oll
read e (index 1) -> olle
read h (index 0) -> olleh

    Compared with the prepending version of this problem, the result is the same, but the work is different. Prepending forces a new string to be built from the whole old result on every pass, so in the simple cost model it is O(n²). Appending to the end of a string is the case JavaScript engines handle well, so the loop stays linear. Each step does a constant amount of work apart from that append, and there are n steps.

    Step by step

    1. Create the result. Declare reversedString with let, typed as string and set to "".
    2. Loop over the indexes from the last to the first. Declare i with let and start it at input.length - 1, the last valid index. Keep going while i >= 0, and decrement with i-- after each pass.
    3. Append the character at index i. Assign reversedString + input[i] back to reversedString. The old result stays on the left, and the new character goes on the right.
    4. Return the result once the loop ends.

    The solution in TypeScript

    class Solution {
    reverse(input: string): string {
        let reversedString: string = "";
        for (let i = input.length - 1; i >= 0; i--) {
            reversedString = reversedString + input[i];
        }
        return reversedString;
    }
}

    The TypeScript details worth a closer look:

    • The annotation is optional. let reversedString: string = "" and let reversedString = "" mean the same thing, because TypeScript infers string. The annotation is erased when the code is compiled, so it doesn't affect the running program.
    • Counting down. The loop starts at the last index, tests i >= 0 and decrements. The test must be >=: with i > 0 the loop would stop before index 0 and the first character of the input would be missing.
    • input[i] is a one-character string. TypeScript has no separate character type, so adding it to a string just joins two strings.
    • No error for a bad index. Reading input[-1] or input[input.length] gives undefined, not an exception, and reversedString + undefined would add the text "undefined". Correct bounds matter.
    • Code units. Indexing works on 16-bit units. For letters and digits that is one unit per character. A character such as an emoji takes two units, and this loop reverses the two halves separately, which breaks the character. A for...of loop keeps such characters whole.
    • Equivalent shorter form. reversedString += input[i] does the same as the longer assignment in the solution.

    Complexity

    Time: O(n). The loop runs once per character. Each pass reads one character and appends it to the end of the result, which the engine handles efficiently, so the total grows linearly with n.

    Space: O(n). The result holds n characters. Strings are immutable, so the result can't be built in place, but only the result itself needs to be kept at the end.

    Edge cases and common mistakes

    • Empty string. input.length - 1 is -1, the test i >= 0 fails at once, and the function returns "".
    • One character. The loop runs once, at index 0, and returns the same character.
    • Starting at input.length. The first read is input[input.length], which is undefined, so the output would begin with the text "undefined".
    • Stopping at i > 0. The first character of the input is skipped: "hello" would give "olle".
    • Increasing i. Writing i++ by habit moves the index away from 0, so i >= 0 never becomes false and the loop never ends.
    • Prepending in this loop. If you write input[i] + reversedString, you get the original string back, because going backwards and inserting at the front cancel out.

    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