How to Reverse a String

Introduction

We can reverse a string in different ways. We will describe two possible algorithms in this article. We will implement them in Java.

Reverse a String Problem

A String is a sequence of characters. We want to obtain a new String with a sequence reversed.

For example, imagine we have the following String:

String toReverse = "abcdef";

We want to obtain:

"fedcba"

Reverse a String by a Trivial Algorithm

A trivial solution that comes to mind is:

• We create a new array of characters with the same length as the original one
• We traverse the original array starting from the last element and copy each element in the second array starting from its beginning

The Java implementation of the above algorithm is shown in the following JUnit test case:

@Test
public void trivialReverseStringTest() throws Exception {

    String toReverse = "abcdef";
    char[] chArray = toReverse.toCharArray();
    char[] chArrayReversed = new char[chArray.length];

    for (int i = 0, j = chArray.length - 1; i < chArray.length; i++, j--) {
        chArrayReversed[i] = chArray[j];
    }

    System.out.println(chArrayReversed);
    for (int i = 0, j = chArray.length - 1; i < chArray.length; i++, j--) {
        assertEquals(chArrayReversed[i], chArray[j]);
    }

}

Performance Considerations

The time complexity of the above algorithm is O(n) and requires an additional O(1) space due to the use of a new array of characters with the same length as the original one.

Reverse a String in a More Efficient Way

We can improve the algorithm described in the above section, without needing an additional array. This solution comes by reconsidering the previous algorithm a little differently. We pretend we still have an additional array by progressively and simultaneously copying the left values in the right positions and the right values in the left ones.

When we arrive at the middle of the array we stop. If the length of the array is an odd integer the center position will not be affected. We can summarize this algorithm like this:

• We start a loop from the first position on the left onwards and at the same time from the last position on the right backwards.
• In each step of the loop, we exchange the left and right values
• We increment the left and decrease the right index of the loop by one until the left index is less than the right one.

The following test shows an implementation of the above description:

@Test
public void reverseStringTest() throws Exception {

    String toReverse = "abcdef";
    char[] chArray = toReverse.toCharArray();

    int i = 0, j = chArray.length - 1;
    while (i < j) {
        char temp = chArray[i];
        chArray[i] = chArray[j];
        chArray[j] = temp;
        ++i;
        --j;
    }

    String reversed = String.valueOf(chArray);
    System.out.println(reversed);
    for (int n = 0, m = chArray.length - 1; n < chArray.length; n++, m--) {
        assertEquals(toReverse.toCharArray()[n], chArray[m]);
    }

}

Conclusion

In this article, we have seen how to reverse a String in Java using two different algorithms, improving the space efficiency in the second one. The example code is available on GitHub.