 # Reverse a string

Published , updated
Tags:

This article looks at the interview question - Reverse a string in the most efficient way possible. For example an input of "abc123" will result in the output "321cba".

## Analysis

This is a very common interview question, it tests whether a candidate understands how string concatenation and immutability works. A simple algorithm that does the job loops through each character and constructs a string in reverse order.

function reverse (text)
define result ← ""
foreach character c in text
result ← c + result
return result


The above algorithm is not very efficient though. This is because strings are immutable which means they cannot be modified after they are created. The algorithm creates a new string every iteration which takes worst case O(n), making the algorithm O(n^2).

The string can be reversed in O(n) time with a couple of different methods: using StringBuilder to construct the string as above, or by converting the string to a character array and back. The optimal solution largely depends on how strings are handled in the language that the function is being implemented in though.

## Code

public static String reverseViaCharArray(String text) {
char[] charArray = text.toCharArray();
int start = -1;
int end = charArray.length;
while (++start < --end) {
char temp = charArray[start];
charArray[start] = charArray[end];
charArray[end] = temp;
}
return String.valueOf(charArray);
}

public static String reverseViaStringBuilderA(String text) {
StringBuilder sb = new StringBuilder();
for (int i = text.length() - 1; i >= 0; i--) {
sb.append(text.charAt(i));
}
return sb.toString();
}

public static String reverseViaStringBuilderB(String text) {
return new StringBuilder(text).reverse().toString();
}
function reverseString(text) {
var result = '';
for (var i = text.length - 1; i >= 0; i--) {
result += text[i];
}
return result;
}

## Textbooks

Here are two textbooks that provide many Q&A's like this post that I personally recommend, both were invaluable to me when I was studying for my interviews.