Saturday 29 June 2013

Algorithm: Reverse a string


Reverse a string in the most efficient way possible. For example an input of "abc123" will result in the output "321cba".


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.


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);


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


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