[Solved] How to reverse a 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 classes or methods like StringBuilder to solve this problem. This restriction is placed because StringBuilder and StringBuffer class define a reverse() method which can easily reverse the given String. Since the main objective of this question is to test the programming skill and coding logic of the candidate, there is no point in giving him the option to use the library method which can make this question trivial. 

Now, how do you solve this problem? If you are familiar with an array data structure then it would be easy for you. 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 the other pointer starts from the end of the array. You swap elements until they meet. At that point in time, your String or array is already reversed.

This is an acceptable solution because we have not used additional memory and any library method, but you can also be asked to explain the time and space complexity of your solution.

The time 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 the 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 in interviews and you will often see a couple of String based coding questions on interviews. Good knowledge of String along with other data structures like an array, linked list, and binary tree is very important. 

If you feel you lack that knowledge or want to improve it, I suggest you take a look at Data Structures and Algorithms: Deep Dive Using Java course on Udemy. It's both an affordable and very comprehensive course and I highly recommend it for Java programmers.




Algorithm to Reverse a String in Place in Java

Here is a 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 integer variables to hold positions from start and end.

If you look closely this algorithm is similar to the algorithm we have earlier 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 likes to see.  If you don't know how to write production-quality code, I suggest you take a look at the Clean Code, one of the books you should read at the start of your programming career.

Btw, if you are not familiar with recursion and iteration or basic fundamentals of Data Structures and Algorithms then I suggest you join a comprehensive course like Algorithms and Data Structures - Part 1 and 2 on Pluralsight to learn them well. It makes a lot of sense to solve problems like this when you know fundamentals better.

Here is the iterative algorithm to reverse String in place:

iterative algorithm to reverse String in place in Java







Java Program to Reverse a Given String in Place - Example

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 used the main() method to test the code, instead I have written a couple of JUnit test cases. It's actually better to write unit test cases all the time to test your code instead of using the main() method as it put unit testing in your habit.

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

I have written the 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 a string with the same character
  • Reverse a String with a different character
  • Reverse an anagram String

And, here is the result of running these JUnit tests:

how to reverse a given string in place in Java



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

Btw, If you are preparing for coding interviews then I also recommend Grokking the Coding Interview: Patterns for Coding Questions on Educative, an interactive portal to prepare for coding interviews.

This text-based course will teach you some 16 useful coding patterns like Sliding Window, Two Pointers, Fast and Slow Pointers, Merge Intervals, Cyclic Sort, and Top K elements that can help you to solve many frequently asked coding problems on interview. It will also make you a better programmer because you know how to solve an unseen problem using existing patterns.

That's all about how to reverse String in place in Java. This is a common algorithm that uses two pointer approach. Since it requires us to traverse the array till the middle, the 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)
  • Top 5 Courses to learn Data Structure and Algorithms (courses)
  • How to reverse String in Java without StringBuffer? (solution)
  • Top 50 Data Structure and Algorithms Interview Questions (list)
  • How to count the number of words in a given String? (solution)
  • Top 5 Books to learn Data Structure and Algorithms (Books)
  • How to check if a String is a palindrome in Java? (solution)
  • Top 5 Courses to learn Dynamic Programming for Interviews (courses)
  • How to find duplicate characters on String? (solution)
  • How to find one missing number in a sorted array? (solution)
  • How to remove an element from an array in Java? (solution)
  • How to count vowels and consonants in a given String? (solution)
  • Top 30 linked list coding interview questions (see here)
  • Top 50 Java Programs from Coding Interviews (see here)
  • 5 Free Data Structure and Algorithms Courses for Programmers (courses)
  • 10 Algorithms Books Every Programmer Should Read (books)
  • 10 Free Data Structure and Algorithm Courses for Programmers (courses)
  • How to reverse words in a given String in Java? (solution)
  • 21 String Programming Questions for Programmers (questions)
  • 100+ Data Structure and Algorithms Questions for Java programmers (questions)
  • 75+ Programming and Coding Interview questions (questions)

Thanks for reading this article so far. If you like this coding question then please share it with your friends and colleagues. If you have any doubts or feedback then please drop a note. You can also follow me on Twitter (javinpaul) to get updates about programming and Java in general.

P. S. - If you are looking for some Free Algorithms courses to improve your understanding of Data Structure and Algorithms, then you should also check the Data Structure in Java free course on Udemy. It's completely free and all you need to do is create a free Udemy account to enroll in this course.

9 comments:

  1. Sorry, but Strings are immutable in Java. This post makes no mention of this extremely important fact. While it is true that the time complexity of the algorithm is O(n) and the space complexity is O(1), both the toCharArray() method and the new String(char[] buffer) constructor make COPIES of their arrays. This example is NOT reversal in place as that's not possible in Java (without unsafe shenanigans) and it does require the use of extra memory (the original String plus at least two array copies.

    ReplyDelete
  2. How come it is O(1) space if this code creates a new array of characters?

    ReplyDelete
    Replies
    1. My mistake! The original article states that the algorithm is O(1) because it (wrongly) says it only uses 2 new variables regards of size of the string. Because two new arrays of the same size of the string are created the space needed will be either 3N or 2N, depending on whether or not you include the original string. Either way, the space complexity is O(n). That is, the space needed grows linearly with the size of the string.

      Delete
  3. void reverse( String A)
    {
    char[] yArray = new char[A.length()];
    char xArray[] =new char[A.length()];
    A.getChars(0, A.length(), xArray, 0);
    System.out.println(xArray);
    int j=xArray.length;
    for(int i=0;i<xArray.length; i++)
    {
    yArray[i]=xArray[j-1];
    j--;
    System.out.println("character pushed at "+i+" is "+yArray[i]);
    }
    System.out.println("Reversed String is : ");
    System.out.println(yArray);
    }

    ReplyDelete
  4. //simple & efficient way without even declaring 3rd variable
    public static void reversingUsingSwappingLogic(String str) {

    char[] ca = str.toCharArray();

    for(int i = 0; i < str.length()/2; i++) {

    ca[i] = (char) (ca[i] ^ ca[ca.length - 1 - i]);
    ca[ca.length - 1 - i] = (char) (ca[i] ^ ca[ca.length - 1 - i]);
    ca[i] = (char) (ca[i] ^ ca[ca.length - 1 - i]);

    }
    str = new String(ca);
    System.out.println(str);

    }

    ReplyDelete
  5. public class MyClass {
    public static void main(String args[]) {
    String s= "Nikunj";
    Character temp=null;
    char[] c= s.toCharArray();
    for(int i=0;i<c.length/2;i++){
    temp=c[i];
    c[i]=c[c.length-(i+1)];
    c[c.length-(i+1)]=temp;
    }
    for(Character ccc:c)
    System.out.print(ccc);
    }
    }

    ReplyDelete
  6. //THIS CODE WILL GIVE THE DESIRED RESULT.

    string str;
    cin>>str;
    for(int i=str.size(); i>=0; i--)
    {
    cout<<str[i];
    }

    ReplyDelete
  7. //This is Using the toCharArray() function to reverse a string in Java

    public static String reverse(String str)
    {
    String rev="";
    char[] finalarray = str.toCharArray();
    for (int i = finalarray.length - 1; i >= 0; i--)
    rev+=finalarray[i];
    return rev;
    }
    //Sample Input- "Scaler Academy"
    //Sample Output-"ymedacA relacS"




    Reference: https://www.scaler.com/topics/reverse-a-string-in-java/

    ReplyDelete
  8. here's the simplest way using a for loop, I think
    public static String reverseString(String s){
    char [] a = s.toCharArray();
    for(int i=0, j=s.length()-1; i<j; i++, j--) {
    char temp = a[i];
    a[i] = a[j];
    a[j] = temp;
    }
    return new String(a);
    }

    ReplyDelete

Feel free to comment, ask questions if you have any doubt.