2 Ways to check if A String is rotation of other in Java?

Write a program to check if one String is a rotation of another String is a common coding problem you will see on programming job interviews.  A String is said to be a rotation of another String, if it has the same length, contains same characters, and they were rotated around one of the characters. For example,  String"bcda" is a rotation of "abcd" but "bdca" is not a rotation of String "abcd". One of the simplest solutions to this interesting problem is first to check if two String has the same length, if not then one String cannot be the rotation of another. If they are of the same length then just create another String by concatenating first String with itself, now check if second String is a substring of this concatenated String or not, if yes, then second String is a rotation of first.

You might be wondering, how does this solution work? Well, you can rotate the String around some character and if you join the String with itself then it actually contains all rotated version of itself. So, when you check the rotated string is part of this concatenated String using contains() method, it returns true, if it is, otherwise false.

Let's understand this with an example, Suppose "JavaProgrammer" is first String and "ProgrammerJava" is second String.You can rotate String around any character starting from index 0, which is 'J' to index=length-1, which is 'r'.

Now if you concatenate "JavaProgrammer" with itself, you get "JavaProgrammerJavaProgrammer", now you can see that it contains every possible rotation of first string. This is one of the superb solutions and when I first learned about it, I was as amazed as you are now.

Btw, if interviewer will ask you how to solve this problem without using String concatenation then what do you do? I'll show you how to do that in this article.



Problem:
Given two string s1 and s2 how will you check if s1 is a rotated version of s2?

Solution
As I said, there are two ways to solve this problem, first, is using String concatenation and secondly is without String concatenation.

The logic of Solution 1:
Here are the steps to check if a String is a rotation of another String by using String concatenation:
  1. Concatenate two string s1 and s2 using + operator. You can also use StringBuffer or StringBuilder if you want to, but + looks nice and clean and it also uses StirngBuilder internally (see Effective Java).
  2. Check if rotated version is present in the concatenated version by using contains() method.


The logic of Solution 2:
Here are the steps to check if a given String s2 is the rotation of String s1 without using String concatenation.
  1. Check if the length of both Strings is same or not, If not then they are not rotation. If yes, then proceed to next step.
  2. Check if both Strings are equal, if yes then s2 is a rotation of s1. If not, then move to next step.
  3. Take the first string's first character and find the index in the second string. If not found, then it's not the rotation, but if found, proceed to next step. 
  4. Subtract the length of the rotated string with the index found to find the final position. 
  5. Check if the first character of the rotated String is same as the character at the final position of input String and the input.substring(finalPos) is equal to the rotated.substring(0, index) .
You can use any solution to solve the problem if there is no restriction, but use the second solution if Interviewer doesn't allow String concatenation.



Java Program to find if a given String is rotation of another String

package dto;

/**
 * Java Program to check if one String is rotation of other. In this program, we
 * will see two solution of this interesting problem, one by using String
 * concatenation and other without using String concatenation.
 * 
 * @author Javin
 */

public class RotateStringDemo {

    public static void main(String args[]) {
        String test = "abcd";
        String rotated = "dabc";

        boolean isRotated = isRotatedVersion(test, rotated);

        System.out.printf("Is '%s' is rotation of '%s' : %b %n", rotated, test,
                isRotated);
    }

    /**
     * Returns true if one string is rotation of another, nulls are not
     * considered rotation of each other
     * 
     * @param str
     * @param rotated
     * @return true if rotated is rotation of String str
     */
    public static boolean isRotatedVersion(String str, String rotated) {
        boolean isRotated = false;

        if (str == null || rotated == null) {
            return false;

        } else if (str.length() != rotated.length()) {
            isRotated = false;

        } else {
            String concatenated = str + str;
            isRotated = concatenated.contains(rotated);
        }

        return isRotated;
    }

    /**
     * Return true if rotated is rotation of input String
     * 
     * @param input
     * @param rotated
     * @return true if one String is rotation of other
     */
    public static boolean isRotated(String input, String rotated) {

        if (input == null || rotated == null) {
            return false;

        } else if (input.length() != rotated.length()) {
            return false;

        }

        int index = rotated.indexOf(input.charAt(0));
        if (index > -1) {

            if (input.equalsIgnoreCase(rotated)) {
                return true;
            }

            int finalPos = rotated.length() - index;
            return rotated.charAt(0) == input.charAt(finalPos)
                    && input.substring(finalPos).equals(
                            rotated.substring(0, index));
        }
        return false;

    }
}

Output
Is 'dabc' is rotation of 'abcd' : true 



JUnit Tests

Here are some unit tests to verify both versions of String rotation logic. This is written using JUnit 4 library hence you need to include junit4.jar into your classpath to run these tests. The @Test annotation is used to create test methods, which will be run by JUnit Runner. See JUnit in Action to learn more about How JUnit works and How it executes test cases.

public class StringRotateDemo {

    @Test
    public void testIsRotatedVersion(){
        assertTrue(isRotatedVersion("abc", "bca"));
        assertTrue(isRotatedVersion("abc", "cab"));
        assertFalse(isRotatedVersion("abc", "bac"));
        assertFalse(isRotatedVersion("abc", null));
        assertFalse(isRotatedVersion("abc", ""));
    }
    
    
    @Test
    public void testisRotated(){
        assertTrue(isRotated("1234", "2341"));
        assertTrue(isRotated("1234", "3412"));
        assertTrue(isRotated("1234", "4123"));
        assertFalse(isRotated("1234", "23s41"));
        assertFalse(isRotated("1234", null));
        assertFalse(isRotated("1234", ""));
    }
}

Output
All test passed

here is the screenshot which shows that all JUnit test is passing and our code is working fine in most of the conditions. You can add more unit tests if you want to. If you are not comfortable with writing unit tests or lack imagination and technique to unit test your code, I suggest you to first read the Test Driven book. It is one of the best books on unit testing and test driven development and will teach you how to effectively test your code, both concepts, and tools.

How to check if A String is rotation of other in Java?



That's all about how to check if two String is rotations of each other in Java. The simplest solution is to just concatenate both original and rotated String and check if the rotation is present in the big, joined String. This is an amazing solution because when you join original and rotated version, it contains every single, possible rotation of the first string. If given rotation is present in the concatenated String, then its definitely is the rotation of given String.

More String Problems to solve
If you are interested in solving more String based algorithm problems then here is the list of some of the frequently asked questions.
  • How to Print duplicate characters from String? (solution)
  • How to check if two Strings are anagrams of each other? (solution)
  • How to program to print first non-repeated character from String? (solution)
  • How to reverse String in Java using Iteration and Recursion? (solution)
  • How to check if a String contains only digits?  (solution)
  • How to find duplicate characters in a String? (solution)
  • How to count the number of vowels and consonants in a String? (solution)
  • How to count the occurrence of a given character in String? (solution)
  • How to convert numeric String to an int? (solution)
  • How to find all permutations of String? (solution)
  • How to reverse words in a sentence without using library method? (solution)
  • How to check if String is Palindrome?(solution)
  • How to return highest occurred character in a String? (solution)
  • How to reverse a String in place in Java? (solution)

Further Reading
Cracking the Coding Interview - 189 Problems and Solutions
Java Programming Interview Exposed by Noel Markham
Algorithm Design Manual By Steve Skiena 

Thanks for reading this coding interview question so far. If you like this String interview question then please share with your friends and colleagues. If you have any question or feedback then please drop a comment. 

8 comments :

Shivam Chopra said...

Hi,

I checked the method 2 and it will fail in case of different letters in the string. Eg : str1 = "abcdef", str2 = "cdefab" so in this case it will return true but if the strings are str1 = "azcdef", str2 = "cdefax" even then it will return true.

So the return statement in method 2 should be :

return rotated.substring(index, rotated.length()).equalsIgnoreCase(input.substring(0, finalPos))
&& input.substring(finalPos).equalsIgnoreCase(rotated.substring(0, index));

Abhi Andhariya said...

Hi Javin

Nice Article. First solution is very impressive.

However your second solution will not work when there are repetitive characters in the string. For Example,

String abcdaba and dabaabc, will return true in case of first solution, But false in case of second solution.

keep sharing such good articles :)

Thanks
Abhi



Javin Paul said...

Hello Abhi and Shubham, thanks for testing the code with different input, it seems second method has some issues, I'll check it further.

saurabh said...

Hi Javin,
Nice observation of concatinating strings.
But instead of right direction if we are rotating in left direction then this solution fails completely.

saurabh said...

If we are rotating in left direction , contains(reverse(string)+reverse(string)) will give solution.

saurabh said...

In point no 1 of logic of Solution1 you have written as "Concatenate two string s1 and s2 using + operator" but it should be "concatenate string s1 with itself"

Javin Paul said...

Hello Saurabh, you are correct, you need to concatenate String by itself. Also, very good observation by you on rotating left, I am impressed :-). You point a problem and then give a solution in existing code, you move closer to become a rockstar developer :-) that's the way to go.

saurabh said...

Hi Paul, Thanks a lot this word of appreciation it matters a lot to me after all I have learnt so many things from you.

Post a Comment