Saturday, March 12, 2016

How to Reverse a String in place in Java - Example

It's possible to reverse a String in place by using a StringBuilder. Since String is Immutable in Java, it's not possible to reverse the same String, but you can minimize the number of intermediate String objects by using StringBuilder or StringBuffer, which are mutable. The algorithm to reverse the String in place is similar to the algorithm we have used earlier to reverse an array in place. You need to traverse the String from one end, swapping characters at another end until you reach the middle of the String. At the point characters in your String is reversed. This algorithm only requires one extra character of memory to facilitate the swapping of characters. The time complexity of this algorithm is O(n/2) i.e. O(n) where n is the length of String.

Ideally, whenever you need to reverse a String in your application, you should be using the reverse() method of StringBuilder. This method reverses the character sequence of the String in place. It also handles the surrogate pairs correctly. If there are any surrogate pairs included in the sequence, these are treated as single characters for the reverse operation.

Thus, the order of the high-low surrogates is never reversed. Note that the reverse operation may result in producing surrogate pairs that were unpaired low-surrogates and high-surrogates before the operation. For example, reversing "\uDC00\uD800" produces "\uD800\uDC00" which is a valid surrogate pair.

Java Program to reverse String in place

Here is our sample Java program to solve this problem of reversing String in place i.e.  without using additional memory, barring one or two variables to keep track of positions. In this example, we have reversed String using an iterative algorithm. It first converts String to StringBuilder, so that we can mutate the contents without creating temporary String objects. Then, it goes through StringBuilder and swap characters from both ends until it reaches the midpoint.  At that point, String is reversed, without any additional memory i.e. in place.

This is also one of the popular String based coding question and commonly asked in Java and other programming job interviews. For good practice, you should try solving problems given in Coding Interview questions and Java Programming interview exposed, two of the best books to do well in Java interviews.

How to reverse String in place in Java

Now, let's see the program in action. If you want to run it yourself, you can just copy paste the code in your Eclipse IDE and it will take care of creating the project, package and all. Once created, just right click and run as Java program.

 * Java Program to replace a String in place.
 * Since String is Immutable in Java, you cannot reverse
 * the same String, but a new String is get created.
 * This program reverse a string in place using StringBuilder

public class Main {

    public static void main(String args[]) {

        String number = "1234";
        System.out.println("original String: " + number);
        String reversed = inPlaceReverse(number);
        System.out.println("reversed String: " + reversed);

     * Java method to replace a String in place
    public static String inPlaceReverse(final String input) {
        final StringBuilder builder = new StringBuilder(input);
        int length = builder.length();
        for (int i = 0; i < length / 2; i++) {
            final char current = builder.charAt(i);
            final int otherEnd = length - i - 1;
            builder.setCharAt(i, builder.charAt(otherEnd)); // swap
            builder.setCharAt(otherEnd, current);

        return builder.toString();
original String: 1234
reversed String: 4321

You can see, we are not creating new String objects, instead just swapping characters in StringBuilder. A common mistake many Java programmer makes while using this algorithm is to traverse the whole String, rather than stopping midway.

It's the same mistake, we have talked about while reversing ArrayList in place. If you traverse the whole String, you switch each character twice, and they will return to their original position, leaving String same an original.

Here is a nice diagram to explain this logic of reversing String in place, you can see how swapping of characters happens at each pass in our loop:

Java program to reverse String in place

That's all about how to reverse a String in place in Java. You can use the same algorithm to reverse any array e.g. int or String array in Java as well. After all, String is also backed by a character array in Java. For further preparation, you can also try to reverse a singly linked list in Java without recursion. It's a little bit tricky but if you apply logic, it can be done. I am anyway, explain that in coming articles.

Further Learning
The Coding Interview Bootcamp: Algorithms + Data Structures
Data Structures and Algorithms: Deep Dive Using Java
Algorithms and Data Structures - Part 1 and 2

1 comment :

Anonymous said...

This algorithm isn't O(n/2) complexity, rather it stays at O(n) complexity, no matter how you are executing your statements (and mostly, c*O(n) == O(n), see wiki:

Post a Comment