Jobs

Interviews

Discussions

Reverse String

Easy

Asked by:

More companies

199 views

Topics:

ArraysStringsTwo Pointers

Write a function that reverses a string. The input string is given as an array of characters s.

You must do this by modifying the input array in-place with O(1) extra memory.

Example 1:

Input: s = ["h","e","l","l","o"]
Output: ["o","l","l","e","h"]

Example 2:

Input: s = ["H","a","n","n","a","h"]
Output: ["h","a","n","n","a","H"]

Constraints:

1 <= s.length <= 10⁵
s[i] is a printable ascii character.

Try coding it in LeetCode

Reverse String

Easy

Asked by:

More companies

199 views

Topics:

ArraysStringsTwo Pointers

Write a function that reverses a string. The input string is given as an array of characters s.

You must do this by modifying the input array in-place with O(1) extra memory.

Example 1:

Input: s = ["h","e","l","l","o"]
Output: ["o","l","l","e","h"]

Example 2:

Input: s = ["H","a","n","n","a","h"]
Output: ["h","a","n","n","a","H"]

Constraints:

1 <= s.length <= 10⁵
s[i] is a printable ascii character.

Try coding it in LeetCode

Solution

Clarifying Questions

When you get asked this question in a real-life environment, it will often be ambiguous (especially at FAANG). Make sure to ask these questions in that case:

The problem states the input is a string. In many languages like Python or Java, strings are immutable. Should I assume the input is given as a mutable data structure, like an array of characters, to allow for an in-place modification?
What is the character set of the string? For example, is it limited to ASCII, or can it contain multi-byte Unicode characters, like emojis, which might affect how I swap elements?
What should be the behavior for an empty string or a string with a single character?
Are there any constraints on the length of the string? For instance, could it be extremely long, requiring me to be mindful of memory usage for any helper variables?
Could the input itself be null or undefined, and if so, how should my function handle that case?

Brute Force Solution

Approach

The most straightforward way to reverse a string is to create a brand new, empty string. Then, we can build the reversed version by adding characters to this new string one by one, starting from the end of the original string.

Here's how the algorithm would work step-by-step:

First, get a new, empty container ready to hold the reversed text.
Look at the very last character of the original text.
Take that character and place it as the first character in your new container.
Next, look at the second-to-last character of the original text.
Take that character and place it right after the character you just added to the new container.
Continue this process, moving backward through the original text one character at a time.
Keep adding each character to the end of your new, growing string.
Once you've taken the very first character of the original text and added it to the end of your new one, you are finished.
The new container now holds the original text in perfect reverse order.

Code Implementation

def reverse_string_brute_force(original_string):
    # Prepare a new container to build the reversed string piece by piece.
    reversed_characters = []

    # Iterate backwards through the original string to access characters in reverse order.
    for character_index in range(len(original_string) - 1, -1, -1):
        character_to_append = original_string[character_index]
        reversed_characters.append(character_to_append)

    # Join the collected characters to form the final reversed string.
    return "".join(reversed_characters)

Big(O) Analysis

Time Complexity

O(n) – The time complexity is determined by the process of iterating through the original string. We must visit each character of the input string exactly once to append it to our new string. If the input string has a length of n, this means we will perform n append operations. Therefore, the total number of operations grows linearly with the size of the input string, which simplifies to O(n).

Space Complexity

O(N) – The algorithm explicitly creates a 'new, empty container' to build the reversed string. This new container will grow to hold every character from the original text. Therefore, the auxiliary space required is directly proportional to the number of characters in the input string, which we denote as N. The space used by this new container scales linearly with the input size.

Optimal Solution

Approach

The most efficient way to reverse a sequence of characters is to swap pairs of characters from opposite ends, gradually working inward. This avoids creating a new copy and modifies the original sequence directly.

Here's how the algorithm would work step-by-step:

Imagine the sequence of characters written out in a line.
Take the very first character and the very last character and have them trade places.
Next, move inward one step from both ends. Take the second character and the second-to-last character and swap them.
Continue this process of swapping the outermost pair of characters and moving towards the center.
Keep repeating this until you meet in the middle.
Once the two meeting points cross or land on the same spot, the entire sequence will be perfectly reversed.

Code Implementation

def reverse_string(string_as_list):
    """
    Do not return anything, modify string_as_list in-place instead.
    """
    left_pointer = 0
    right_pointer = len(string_as_list) - 1

    # Iterate until the two pointers meet or cross, ensuring the entire string is processed.

    while left_pointer < right_pointer:
        # Swap the characters at the outer ends to reverse their positions.

        temp_char_holder = string_as_list[left_pointer]
        string_as_list[left_pointer] = string_as_list[right_pointer]
        string_as_list[right_pointer] = temp_char_holder

        # Move the pointers inward to process the next pair of characters.

        left_pointer += 1
        right_pointer -= 1

Big(O) Analysis

Time Complexity

O(n) – The time complexity is determined by the number of swaps performed. Let n be the number of characters in the string. The described approach uses two pointers, one at the beginning and one at the end, moving towards the center. In each step, a single swap operation is performed, and both pointers move one position closer. This process continues until the pointers meet or cross in the middle, meaning we iterate through roughly half of the string. The total number of operations is proportional to n/2, which simplifies to O(n) because we drop constant factors.

Space Complexity

O(1) – The algorithm operates by swapping characters directly within the original sequence, modifying it in-place. The only extra memory required is for a single temporary variable to hold a character during the swap operation. Since the amount of extra memory used does not grow with the size of the input string, the space complexity is constant.

Edge Cases

Case	How to Handle
An empty string	The algorithm correctly does nothing as the loop condition for swapping will not be met.
A string with a single character	The algorithm correctly does nothing as the pointers will start at the same position.
A string that is a palindrome	The algorithm will perform swaps but the resulting string will be identical to the original.
A string with all identical characters	The algorithm performs swaps, but since all characters are the same, the string remains unchanged.
A very long string approaching system memory limits	The in-place algorithm has O(1) space complexity, making it highly efficient for large inputs without extra memory allocation.
A string containing non-alphanumeric characters or symbols	The algorithm treats all characters equally, swapping them based on their position regardless of their type.
A string with an even number of characters	The two pointers will cross after the final swap in the middle, correctly terminating the reversal.
A string with an odd number of characters	The two pointers will meet at the middle character, which is not swapped, and the loop terminates correctly.

An empty string

How to Handle:

The algorithm correctly does nothing as the loop condition for swapping will not be met.

A string with a single character

How to Handle:

The algorithm correctly does nothing as the pointers will start at the same position.

A string that is a palindrome

How to Handle:

The algorithm will perform swaps but the resulting string will be identical to the original.

A string with all identical characters

How to Handle:

The algorithm performs swaps, but since all characters are the same, the string remains unchanged.

A very long string approaching system memory limits

How to Handle:

The in-place algorithm has O(1) space complexity, making it highly efficient for large inputs without extra memory allocation.

A string containing non-alphanumeric characters or symbols

How to Handle:

The algorithm treats all characters equally, swapping them based on their position regardless of their type.

A string with an even number of characters

How to Handle:

The two pointers will cross after the final swap in the middle, correctly terminating the reversal.

A string with an odd number of characters

How to Handle:

The two pointers will meet at the middle character, which is not swapped, and the loop terminates correctly.

Solution

Clarifying Questions

When you get asked this question in a real-life environment, it will often be ambiguous (especially at FAANG). Make sure to ask these questions in that case:

The problem states the input is a string. In many languages like Python or Java, strings are immutable. Should I assume the input is given as a mutable data structure, like an array of characters, to allow for an in-place modification?
What is the character set of the string? For example, is it limited to ASCII, or can it contain multi-byte Unicode characters, like emojis, which might affect how I swap elements?
What should be the behavior for an empty string or a string with a single character?
Are there any constraints on the length of the string? For instance, could it be extremely long, requiring me to be mindful of memory usage for any helper variables?
Could the input itself be null or undefined, and if so, how should my function handle that case?

Brute Force Solution

Approach

Here's how the algorithm would work step-by-step:

First, get a new, empty container ready to hold the reversed text.
Look at the very last character of the original text.
Take that character and place it as the first character in your new container.
Next, look at the second-to-last character of the original text.
Take that character and place it right after the character you just added to the new container.
Continue this process, moving backward through the original text one character at a time.
Keep adding each character to the end of your new, growing string.
Once you've taken the very first character of the original text and added it to the end of your new one, you are finished.
The new container now holds the original text in perfect reverse order.

Code Implementation

def reverse_string_brute_force(original_string):
    # Prepare a new container to build the reversed string piece by piece.
    reversed_characters = []

    # Iterate backwards through the original string to access characters in reverse order.
    for character_index in range(len(original_string) - 1, -1, -1):
        character_to_append = original_string[character_index]
        reversed_characters.append(character_to_append)

    # Join the collected characters to form the final reversed string.
    return "".join(reversed_characters)

Big(O) Analysis

Time Complexity

Space Complexity

Optimal Solution

Approach

Here's how the algorithm would work step-by-step:

Imagine the sequence of characters written out in a line.
Take the very first character and the very last character and have them trade places.
Next, move inward one step from both ends. Take the second character and the second-to-last character and swap them.
Continue this process of swapping the outermost pair of characters and moving towards the center.
Keep repeating this until you meet in the middle.
Once the two meeting points cross or land on the same spot, the entire sequence will be perfectly reversed.

Code Implementation

def reverse_string(string_as_list):
    """
    Do not return anything, modify string_as_list in-place instead.
    """
    left_pointer = 0
    right_pointer = len(string_as_list) - 1

    # Iterate until the two pointers meet or cross, ensuring the entire string is processed.

    while left_pointer < right_pointer:
        # Swap the characters at the outer ends to reverse their positions.

        temp_char_holder = string_as_list[left_pointer]
        string_as_list[left_pointer] = string_as_list[right_pointer]
        string_as_list[right_pointer] = temp_char_holder

        # Move the pointers inward to process the next pair of characters.

        left_pointer += 1
        right_pointer -= 1

Big(O) Analysis

Time Complexity

Space Complexity

Edge Cases

Case	How to Handle
An empty string	The algorithm correctly does nothing as the loop condition for swapping will not be met.
A string with a single character	The algorithm correctly does nothing as the pointers will start at the same position.
A string that is a palindrome	The algorithm will perform swaps but the resulting string will be identical to the original.
A string with all identical characters	The algorithm performs swaps, but since all characters are the same, the string remains unchanged.
A very long string approaching system memory limits	The in-place algorithm has O(1) space complexity, making it highly efficient for large inputs without extra memory allocation.
A string containing non-alphanumeric characters or symbols	The algorithm treats all characters equally, swapping them based on their position regardless of their type.
A string with an even number of characters	The two pointers will cross after the final swap in the middle, correctly terminating the reversal.
A string with an odd number of characters	The two pointers will meet at the middle character, which is not swapped, and the loop terminates correctly.

An empty string

How to Handle:

The algorithm correctly does nothing as the loop condition for swapping will not be met.

A string with a single character

How to Handle:

The algorithm correctly does nothing as the pointers will start at the same position.

A string that is a palindrome

How to Handle:

The algorithm will perform swaps but the resulting string will be identical to the original.

A string with all identical characters

How to Handle:

The algorithm performs swaps, but since all characters are the same, the string remains unchanged.

A very long string approaching system memory limits

How to Handle:

The in-place algorithm has O(1) space complexity, making it highly efficient for large inputs without extra memory allocation.

A string containing non-alphanumeric characters or symbols

How to Handle:

The algorithm treats all characters equally, swapping them based on their position regardless of their type.

A string with an even number of characters

How to Handle:

The two pointers will cross after the final swap in the middle, correctly terminating the reversal.

A string with an odd number of characters

How to Handle:

The two pointers will meet at the middle character, which is not swapped, and the loop terminates correctly.