When working strings there are any number of operations you might need to perform. One operation is to reverse a string.

• Some examples
• An algorithm
• A better algorithm
• Swap 1
• Swap 2
• Why would you reverse a string?

Some examples

When demonstrating an algorithm it often helps to have some simple examples to follow. What are some simple strings that we might use for demonstration? How about English words that when reversed are a different word. I am not talking about a [palindrome](https://en.wikipedia.org/wiki/Palindrome "palindrome article"), rather I am referring to words that when reversed make entirely different words.

An algorithm

There are many different ways to reverse a string. Some languages support reversing a string easily while others do not. Before we get into the specifics of any language we should first define one algorithm for performing the reversal.

set len = current_string length
initialize empty string reverse_string of length len
set current_index to last index of current_string.
set next_index to index 0 of reverse_string
while current_index is greater than first index of current_string
  copy character at current_index to next_index
  move current_index to the left by one position in current_string
  move next_index to the right by one position in reverse_string
end while  

If you follow the algorithm above you will have a new string that is the reverse of the first and will require 4 iterations of the while loop to reverse the string and use two string variables.
The first string has the value of the string to be reversed. The second string starts as an empty string that is the same size as the first string.

0123 0123

TIME     

After the first operation the last letter will be in the first position of the new string.

0123 0123

TIME E   

The next assignment will result in one more letter being assigned to the new string..

0123 0123

TIME EM  

One more assignment

0123 0123

TIME EMI 

Finally, the last letter will be assigned.

0123 0123

TIME EMIT

The result is the string reversed.

This algorithm has a time complexity of O(n) and a space complexity of O(n). We are ignoring the space used by the original string since that memory is already allocated outside of the algorithm.

The algorithm must iterate the while loop four times, or the length of the string, to complete. This is where the O(n) time complexity is determined.

In order to reverse the string another variable the same size as the original string must be created. This means that the algoritm will use the space of the original string length (n) as well as the space for the new reversed string. This results in the space complexity of O(n).

A better algorithm

Another algorithm that will result in less time and space complexity will keep track of the beginning and end of the string and use only a single byte of extra memory.

In this algorithm the current characters being moved is stored in a temporary variable. The two letters are then swapped and the indexes for the first and last character to swap are moved.

set index i to index 0 of current_string (The first character)
set index j to last index of current_string (length of current_string - 1)
while index j is greater than index i
  assign character at index i to tmp
  assign character at index j to index i
  assign character in tmp to index j
  increment index i to right by one position
  decrement index j to left by one position
end while

This results in two iterations instead of 4.

Here is how it looks for each step.

Swap 1

Swap 2

The time and space complexity is improved for this algorithm. The time complexity is now O(n/2) and the space complexity is O(1). Again, we ignore the space allocated by the original string since it is being allocated outside the algorithm.

The number of iterations to reverse the string is now looping half as many times. Instead of looping once for each character and assigning that character to a new string each time we only need to loop until we have swapped half of the characters. In this algorithm we still make as similar number of operations, so we are not saving much on the actual operations front.

The real savings is on the space complexity. In the previous algorithm we had to allocate enough space to store the reversed string. This meant that the amount of space used would grow as the size of the input string grew. In this algorithm we only need enough memory to store a single character. This means that the memory requirements of the algorightm to not depend on the size of the input string.

Why would you reverse a string?

Great question. Other than to show off your skills in a coding interview, what have you used a reverse string algorithm for?