Algorithm: Reverse a string

Problem

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.

Code

View on GitHub

Char array

String reverse(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);
}

StringBuilder

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

or

public static String reverse(String text) {
    return new StringBuilder(text).reverse().toString();
}