How to Reverse a String in place in Java - Example (original) (raw)

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 are 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 mean 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.

Also, basic knowledge of essential data structure is also very important and that's why I suggest all Java programmers join a comprehensive Data Structure and Algorithms course. If you need recommendations you can check out this list of best data Structure and algorithms online courses to fill the gaps in your understanding.

Java Program to reverse String in place - Example

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 swaps 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 questions and commonly asked in Java and other programming job interviews. For good practice, you should try solving problems given in these coding interview courses, one of the best resources to do well in Java interviews.

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

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 a Java program.

/*

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

} Output 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 the same as the original.

That's all about how to reverse a String in place in Java. You can use the same algorithm to reverse any array like integer 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.

Other Java Coding Problems for Practice

Thanks for reading this coding interview question so far. If you have any doubt or questions feel free to ask, happy to answer. I also have an exercise for you? can you find out the time and space complexity of this solution? Also, is there a way to better this solution?