Category: Python

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

Input: A = [“h”,”e”,”l”,”l”,”o”]
Output: [“o”,”l”,”l”,”e”,”h”]

Solution #1: Arrays ie., lists in Python are mutable data structures which means they can be modified in place without having to allocate extra space. For this problem, creating a new array using the input array is a trivial solution. So let’s directly dive into an O(1) memory solution.

In Python, we can refer to the elements in reverse order starting at the index -1.

A[-1] = “o”

A[-2] = “l”

A[-5] = “h”

This is quite helpful in manipulating array indexes. In order to reverse the elements, we don’t have to traverse the full list but swap the first half of the list with the second half starting from the end.

ie., swap A[i] with A[-(i+1)] for i = 0 to i = len(A) / 2

Time Complexity: We traverse only half the list while swapping elements with the second half of the list. So the time complexity will be O(N/2) which is O(N) overall.

Space Complexity: O(1)

Code for solution #1:

def reverseString(self, s: List[str]) -> None:
    """
    Do not return anything, modify s in-place instead.
    """
    for i in range(len(s) // 2):
        s[i], s[-(i+1)] = s[-(i+1)], s[i]

Solution #2: A Python in-built function that does exactly what we did above is reverse(). The list is modified in place by swapping the first half of the list with the second half the same way as shown above. Read more about reverse() here.

Code for solution #2:

def reverseString(self, s: List[str]) -> None:
    s.reverse()

Time Complexity: O(N)

Space Complexity: O(1)

Solution #3: If we are allowed to create and return a new list, then we can use Python reversed() function as shown below. reversed() returns an iterator in Python, so we have to wrap its result in a list(). Read more about it here.

Code for solution #3:

def reverseString(self, s: List[str]) -> List[str]:
    return list(reversed(s))

Time Complexity: O(N)

Space Complexity: O(N) since we are creating a new list.

What if we are given a string and not an array of characters?

An important distinction here is that strings are immutable, so we cannot leverage any in-place reversals here. Let’s look at some Pythonic ways of reversing a string.

Input: “hello”

Output: “olleh”

Solution #4: Using Python’s elegant index slicing.

Code for solution #4:

def reverseString(self, s: str) -> str:
    return s[::-1]

Okay, what was that? In Python there is a concept called slicing. The syntax for slicing is shown below.

A[start: stop: step]

• start – The index to start slicing (default: 0)
• stop – The index to stop slicing (default: len(s))
• step – The increment between each index for slicing

Examples:

• A[0:1] slices the first element
• A[1:4] slices the elements from index 1 to 3

The -1 step in the code indicates that we will start at the end and stop at the start instead of the other way around, thereby reversing the string.

Read more about Python slicing here.

Time Complexity: O(N)

Space Complexity: O(N) since a new string is created.

Solution #5: Another way to improve the readability of your code instead of using the above syntax which a non-python developer may not immediately be able to comprehend is to use reversed() to reverse a string.

• Use reversed() to create an iterator of the string characters in the reverse order.
• Use join to merge all the characters returned by the iterator in the reverse order.

def reverseString(self, s: str) -> str:
    return "".join(reversed(s))

Time Complexity: O(N)

Space Complexity: O(N) since a new string is created.

Let’s summarize all the different ways.

Hope you learnt many Pythonic ways to reverse a string or an array of chars[]. There are many non-Pythonic ways as well which we will discuss in a separate post. Have a great day!