Practice: Reverse a String

Introduction

In this practice session, we will maintain our theme of using two pointers to solve problems efficiently.

Problem statement

The task is to reverse a given string. We aren’t allowed to use extra memory. We’re also not allowed to use more than one loop, that is, the complexity should be $O(n)$.

Example input and output

Input 1:

"abcd"

Output 1:

"dcba"

We have to reverse the characters in the string. The characters can be anything (letters or numbers).

Input 2:

""

Output 2:

""

The reverse of the empty string is the empty string.

Input 3:

"a"

Output 3:

"a"

The reverse of “a” is the string “a”.

Two pointers solution

We’ll solve this problem in an efficient way by using the two-pointers approach. Since we used this pattern a few times, you are welcome to try to solve this problem before reading the solution. It is not mandatory, as this is not a coding challenge, but it will help you master the concepts!

The idea for the solution is to start at both ends of the string and swap these characters together. Then move inwards and repeat the process until there are no more pairs to swap. We use two pointers, start and end, one at the start of the array and one at the end. We use them to swap the characters and then increment start and decrement end as one pointer has to move to the right and one to the left.

The following animation shows the idea behind this solution: