Thursday, May 11, 2023

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

/*
 * 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();
    }
}
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
  • How to check if a LinkedList contains any cycle in Java? (solution)
  • How to find the top two maximum on integer array in Java? (solution)
  • How to check if a number is Armstrong's number or not? (solution)
  • How to remove duplicates from an array without using Collection API? (program)
  • How to reverse String in Java without using API methods? (Solution)
  • How to check if a number is binary in Java? (answer)
  • Write a program to check if a number is Prime or not? (solution)
  • Write a method to count occurrences of a character in String? (Solution)
  • How do find the largest and smallest number in an array? (solution)
  • Write a function to find the middle element of the linked list in one pass? (solution)
  • How to solve the Producer-Consumer Problem in Java. (solution)
  • How to search an element in an array in Java? (solution)
  • How to sort an array using the bubble sort algorithm? (algorithm)
  • How to calculate Sum of Digits of a number in Java? (Solution)
  • Write a method to remove duplicates from ArrayList in Java? (Solution)
  • Write a method to check if two String are Anagram of each other? (method)
  • Write a program to find the first non-repeated characters from String in Java? (program)
  • Write a program to check if a number is a Palindrome or not? (program)
  • Write a program to check if the Array contains a duplicate number or not? (Solution)
  • How to find the Fibonacci sequence up to a given number? (solution)

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?

4 comments:

  1. 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: https://en.wikipedia.org/wiki/Big_O_notation).

    ReplyDelete
  2. we can use below code as well.
    public class StringExample2
    {
    public static void main(String[] args)
    {
    String string = "1234";
    char str[] = string.toCharArray();
    for(int i = string.length()-1; i>=0; i--)
    {
    System.out.print(str[i]);
    }
    }
    }

    ReplyDelete
  3. Hello Javin, could you explain me why is this still an in-place when we are creating a new StringBuilder object. And at the end, we convert a builder to a new string object. (So we create a new String). Just trying to understand. Thanks

    ReplyDelete
  4. Hello Aleksandar, as I have explained in the article, the in place algorithms are the ones which doesn't need to allocate extra memory, barring one or two intermediate variables. It's much more clear when you first solve reverse an array in place. So simplest way to just convert the string to character array and reverse.

    Now, you may know that String is Immutable in Java and any mutation will create new string for example taking out one character from beginning and putting into end, hence we are using StringBuffer.

    The use of StringBuffer here is not to allocate extra memory but facilitate swapping of character which makes this solution in place but if your interviewer argue against that, then just convert to character array and reverse it, that's more safer approach.

    I hope this clarifies your doubt, if you still have any doubt and something is not clear, feel free to ask.

    Have a great day ahead !!

    ReplyDelete