How to Reverse a String [Interview Question + Solution]

How to Reverse a String (With Solutions in Python, Java & JavaScript)

How to Reverse a String: Problem Overview

The Reverse String problem involves taking a given string of characters and reversing the order of the characters. This problem, despite its simplicity, invites many advanced approaches, such as iteration, recursion, or multiple pointers, each presenting a unique time and space complexity tradeoff.

An Example of the Reverse String Problem

Write a program to reverse the given string. The program's output would be a string with all characters in reverse order.

Input: "hello world"
Output: "dlrow olleh"

Input: "aba"
Output: "aba"

Input: "ab"
Output: "ba"

Input: ""
Output: ""

Constraints

The number of characters in the string would be in the range [0, 100000].

How to Reverse a String: 4 Approaches in Python, Java & JavaScript

The most straightforward answer is to use an inbuilt library-provided function that is usually available in most languages. But the interviewer is probably not interested in our knowledge of library functions. This means the ideal solution would be similar to how a library would implement a reverse function (i.e., Python, JavaScript, Ruby). There are several approaches, and we'll discuss some of them here.

Approach 1: Build String Iteratively (Brute Force)

We can loop through each character of the original string and build the reversed string iteratively. We start with an empty string and append the characters to it as we loop across the original string. Please note that we are appending the characters to the beginning of the string. By doing so, we ensure that the characters appearing later in the original string appear earlier in the reversed string.

Algorithm

  1. Initialize an empty string reversed_string.
  2. Loop through each character of the original string.
  3. Append the character at the beginning of reversed_string.
  4. Return the reversed_string.

Reverse String JavaScript, Python and Java Solutions - Brute Force

JavaScript

function reverseString(string) {
    let reversedString = "";
    for (char of string) {
        reversedString = char + reversedString;
    }
    return reversedString;
}

Time/Space Complexity

Approach 2: Build String Iteratively (Linear Time)

Instead of creating a new string every time we need to find a data structure that we can append individual characters to in constant time, and to this we can use a stack. A stack is a data structure that follows the LIFO principle. In this approach, we push all the characters of the original string onto the stack and then pop them one by one in order to build the reversed string.

Algorithm

  1. Initialize an empty stack stack.
  2. Loop through each character of the original string.
  3. Push the character to the stack.
  4. Initialize an empty dynamic array reversed_string.
  5. Loop until the stack is empty.
  6. Pop the top character from the stack. Append it to the end of reversed_string.
  7. Create a string from the dynamic array reversed_string and return it.

Reverse String Javascript, Python and Java Solutions - Using a Stack

JavaScript

function reverseString(string) {
    let stack = [];
    for (char of string) {
        stack.push(char);
    }
    let reversedString = [];
    while (stack.length > 0) {
        reversedString.push(stack.pop());
    }
    return reversedString.join("");
}

Time/Space Complexity

Approach 3: In Place Reversal (Two Pointers)

In this approach, we can swap the characters at two pointers. We can keep doing this until the two pointers meet each other.

Algorithm

  1. Convert the string to a character array char_array.
  2. Initialize two pointers, start and end, to point at the start and the end of the string, respectively.
  3. Loop until start is less than end.
  4. Swap the characters at start and end.
  5. Increment start and decrement end.
  6. Convert the character array back to a string and return it.

Reverse String Javascript, Python and Java Solutions - Using In Place Reversal

JavaScript

function reverseString(string) {
    let charArray = string.split("");
    let start = 0;
    let end = charArray.length - 1;
    while (start < end) {
        swap(charArray, start, end);
        start += 1;
        end -= 1;
    }
    return charArray.join("");
}

function swap(charArray, start, end) {
    // using destructuring assignment to swap the characters
    [charArray[start], charArray[end]] = [charArray[end], charArray[start]];
}

Time/Space Complexity

Approach 4: In Place Reversal (Recursion)

In the previous approach, we can also use recursion to swap the characters at the index of each pointer.

Algorithm

  1. Convert the string to a character array char_array.
  2. Call the recursive function reverseStringHelper with char_array, 0 and char_array.length - 1 as input.

Recursive function reverseStringHelper:

  1. Base case: If start is greater than end, return.
  2. Swap the characters at start and end.
  3. Call the recursive function reverseStringHelper with char_array, start + 1 and end - 1 as input.

Reverse String Javascript, Python and Java Solutions - Using In Place Reversal with Recursion

JavaScript

function reverseString(string) {
    let charArray = string.split("");
    reverseStringHelper(charArray, 0, charArray.length - 1);
    return charArray.join("");
}

function reverseStringHelper(charArray, start, end) {
    if (start > end) {
        return;
    }
    swap(charArray, start, end);
    reverseStringHelper(charArray, start + 1, end - 1);
}

#### Time/Space Complexity

- Time Complexity: `O(n)`.

- Space Complexity: `O(n)`.

## Reverse String Frequently Asked Questions (FAQ)

### Why can’t you just use reverse() when reversing a string?

In real life, you probably would. However, in an interview, you’ll want to demonstrate to your interviewer that you understand what programming languages do under the hood when they call a function like reverse().

### How do you reverse a string in place?

To reverse a string in place means to modify the original string directly without using any additional memory. There are two ways to do this: the first is iterative, and the second uses recursion.

### What’s the difference between reversing a string and reversing an array of integers?

When reversing a string, you are dealing with a sequence of characters. Strings are typically treated as immutable in many programming languages, including Python, which means you cannot modify them directly.