How to reverse String in place in Java - Example

One of the common Java coding interview questions is to write a program to reverse a String in place in Java, without using additional memory. You cannot use any library method e.g. StringBuilder to solve this problem. This restriction is placed because StringBuilder and StringBuffer class defines a reverse() method which can easily reverse the given String. Since the main objective of this question is to test the programming logic of candidate, there is no point giving him the option to use the library method which can make this question trivial. Now, how do you solve this problem? Since String is backed by a character array, You can use the same in place algorithm we have used to reverse an array in place. That technique uses the two pointer approach where one pointer starts from the beginning and other pointer starts from the end. You swap elements until they meet. At that point of time, your String is already reversed.

The complexity of this algorithm is O(n/2) + time taken in swapping, which effectively adds up to O(n) time. This means time will increase in the proportion of the length of String or number of characters on it.  The space complexity is O(1) because we are not using any additional memory to reverse the String.

Btw, String is a very popular topic on interviews and you will often see a couple of String based coding questions on interviews. You can check, Introduction to Algorithms  by Thomas Cormen to learn more about popular String algorithms.

In place algorithm to reverse String in Java


Java Program to reverse String in place

Here is the simple example to reverse characters in String by using two pointer technique. This is an in-place algorithm because it doesn't allocate any extra array, it just uses the two int variables to hold positions from start and end. If you look closely this algorithm is similar to the algorithm we have used to reverse an array in place.

That's obvious because String is backed by character array in Java. If you know how to reverse an array in place then reversing a String is not different for you.  What is more important is checking for null and empty String because this is where many programmers become lazy and started writing code without validating input.


You must write your best code during programming interviews. The code which can stand the test of time in production is what every interview like to see.  If you don't know how to write production quality code, I suggest you take a look at Clean Code, one of the books you should read at the start of your programming career.

Here is the iterative algorithm to reverse String in place:

iterative algorithm to reverse String in place in Java


Java Program to reverse a String in Place
import org.junit.Assert;
import org.junit.Test;

/**
 * Java Program to reverse a String in place, 
 * without any additional buffer in Java.
 *
 * @author WINDOWS 8
 *
 */
public class StringReversal {

    /**
     * Java method to reverse a String in place
     * @param str 
     * @return  reverse of String
     */
    public static String reverse(String str) {
        if(str == null || str.isEmpty()){
            return str;
        }
        char[] characters = str.toCharArray();
        int i = 0;
        int j = characters.length - 1;
        while (i < j) {
            swap(characters, i, j);
            i++;
            j--;
        }
        return new String(characters);
    }

    /**
     * Java method to swap two numbers in given array
     * @param str
     * @param i
     * @param j 
     */
    private static void swap(char[] str, int i, int j) {
        char temp = str[i];
        str[i] = str[j];
        str[j] = temp;
    }

    @Test
    public void reverseEmptyString(){
        Assert.assertEquals("", reverse(""));
    }
    
    @Test
    public void reverseString(){
        Assert.assertEquals("cba", reverse("abc"));
    }
    
    @Test
    public void reverseNullString(){
        Assert.assertEquals(null, reverse(null));
    }
    
    @Test
    public void reversePalindromeString(){
        Assert.assertEquals("aba", reverse("aba"));
    }
    
    @Test
    public void reverseSameCharacterString(){
        Assert.assertEquals("aaa", reverse("aaa"));
    }
    
    @Test
    public void reverseAnagramString(){
        Assert.assertEquals("mary", reverse("yram"));
    }
}

You might have also noticed that this time, I have not use the main() method to test the code, instead I have written couple of JUnit test cases. It's actually better to write unit test cases all the time to test your code instead of using main() method as it put unit testing in your habit.

Btw, if you feel reluctance on writing unit tests or not sure how to write tests, I suggest you read Test Driven, one of the best book on Test drive development but even if you don't follow TDD, it will help you to write better code and unit tests.

How to reverse String in place in Java - example

I have written following JUnit tests to check whether our reverse method is working for different kinds of String or not, the JUnit test result is also attached below:
  • Unit test to reverse an empty String
  • Test to reverse a null String
  • Reverse a palindrome String
  • Unit tests to reverse a one character string
  • JUnit test to reverse string with the same character
  • Reverse a String with different character
  • Reverse an anagram String

and here is the result of running these JUnit tests:

How to reverse String in place in Java



You can see that all the unit tests are passing, which is good. You can also add more unit test to further test our method of revrsing String in Java.

That's all about how to reverse String in place in Java. This is a common algorithm which uses two pointer approach. Since it require us to traverse the array till middle, time complexity is O(n/2) i.e. O(n). It doesn't use any external buffer instead just use two variables to keep track of indices from start and end.

Other String based coding problems from Interviews:
  • How to print all permutations of a String using recursion? (solution)
  • How to reverse String in Java without StirngBuffer? (solution)
  • How to count the number of words in given String? (solution)
  • How to check if a String is a palindrome in Java? (solution)
  • How to find duplicate characters on String? (solution)
  • How to count vowels and consonants in given String? (solution)
  • How to reverse words in a given String in Java? (solution)


No comments:

Post a Comment