2 Ways to Check if a String is Rotation of Other in Java - Algorithms

Write a program to check if one String is a rotation of another String is a common coding problem you will find on programming job interviews.  A String is said to be a rotation of another String, if it has the same length, contains the 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, the 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? Don't worryI'll show you how to do that in this article.

And, if you feel you lack Data Structure and Algorithms skills you can revise them by joining Data Structures and Algorithms: Deep Dive Using Java  course, one of the best to learn DS and Algorithms in Java.

2 Ways to Check if a String is Rotation of Other in Java

Now that you are familiar with the problem and solution, along with how exactly this algorithm work, type to write code and solve the problem in a professional way.

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 StringBuilder internally (see Effective Java).

Check if the 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 the next step.

Check if both Strings are equal, if yes then s2 is a rotation of s1. If not, then move to the next step.

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.

Subtract the length of the rotated string with the index found to find the final position.

Check if the first character of the rotated String is the 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. And, if you want to learn more about recursive algorithms, you can also check Algorithms and Data Structures - Part 1 and 2  courses on Pluralsight.

Btw, you would need a Pluralsight membership to get access this course, which cost around $29 per month or $299 annually (14% discount). I suggest every programmer have Pluralsight membership for their learning but if you don't have one, they also provide a 10-day free trial without any commitment, which is a great way to not just access this course for free but also to check the quality of courses before joining Pluralsight.

Java Program to find if a given String is a 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
		

You can see that basic test pass, as given string "dabc" is a rotation of "abcd", where String is rotated around letter "d".   You can further see Data Structures and Algorithms: Deep Dive Using Java  to learn more about String and other Data Structure.

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.

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 the original and rotated version, it contains every single, possible rotation of the first string. If the given rotation is present in the concatenated String, then it's definitely in the rotation of given String.

Further Learning

Data Structures and Algorithms: Deep Dive Using Java

Algorithms and Data Structures - Part 1 and 2

Data Structures in Java by Heinz Kabutz

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)
• 10 Algorithms Courses to Crack Programming Job Interviews (courses)
• How to reverse words in a sentence without using a 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)
• 50+ Data Structure and Algorithms Interview Questions (questions)

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.

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 this list of Free Data Structure and Algorithms Courses for Programmers.