Sunday, October 6, 2019

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).
  2. 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.
  2. Check if both Strings are equal, if yes then s2 is a rotation of s1. If not, then move to the 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 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.

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

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

Jinguang Liu said...

I paste the code which can deal with duplicated characters for solution 2:
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 = 0;
int finalPos = 0;

do {
index = rotated.indexOf(input.charAt(0), index);
if (index < 0) {
return false;
}

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

finalPos = rotated.length() - index;
if (rotated.charAt(0) == input.charAt(finalPos)
&& input.substring(finalPos).equals(rotated.substring(0, index))) {
return true;
}

index += 1;
} while (index < input.length());

return false;
}

Priyal Patel said...

Hello,

i implemented the algo as you described and it is working good.

but, I have one question about string compairision.
when we checked half of the input string with half of the rotated String as you said
input.substring(finalPos) is equal to the rotated.substring(0, index)

now, what about other half? why we are not checking like rotated.substring(index+1) is equal to input.substring(0,finalPos-1)???




--j aneiros said...

Hi Javin et al, I see your second solution still doesn't work (2019-02-19). See mine below. Thanks.

/**
* The function checks if a string is a rotation of another string. By
* rotation we understand the shifting of 1 character without losing that
* character, for example: daabc is a rotated string of abcda, deaabc is a
* rotation of abcdea and dceaab is not a rotation of abcdea.
*
* The fundamental idea behind this solution is that any rotated string is
* just the concatenation of 2 consecutive substrings that forms the
* original one, for example da and abc are 2 substrings from abcda,
* dea and abc are the 2 from abcdea.
*
* The function finds the 2 substrings, concatenates them and returns the
* result of the comparison with the original.
*
* @param s The original string
* @param r The rotated string
* @return A boolean
*/
public static boolean isRotated(String s, String r) {
boolean result = false;

// Take the first char of the original string
char c = s.charAt(0);

// Find the first ocurrence of the char c on the rotated string
// but as the char could be repeated we need to find it
// from the right.
int i = -1;
for (int j = r.length() - 1; j != 0; j--) {
if (c == r.charAt(j)) {
i = j;
break;
}
}

if (i != -1) {
// Extract the 2 substrings
String s1 = r.substring(0, i);
String s2 = r.substring(i);

// Compare the original string with the
// concatenation of the 2 substrings.
result = s.equals(s2 + s1);
}

return result;
}

Javin Paul said...

Hello j anerios, thanks for heads-up and your solution, I will check it and correct if needed.

--j aneiros said...

Thanks. The following considers the case of rotation == 0 and the parameters checking.

/**
* The function checks if a string is a rotation of another string. By
* rotation we understand the shifting of 1 or more characters without
* losing them, for example: daabc is a rotated string of abcda, deaabc is a
* rotation of abcdea and dceaab is not a rotation of abcdea.
*
* The fundamental idea behind this solution is that any rotated string is
* just the concatenation of 2 consecutive substrings that forms the
* original one, for example da and abc are 2 substrings from abcda, dea and
* abc are the 2 from abcdea.
*
* The function finds the 2 substrings, concatenates them and returns the
* result of the comparison with the original.
*
* The function handles null strings, different length strings and
* ignores case.
*
* @param s The original string
* @param r The rotated string
* @return A boolean
*/
public static boolean isRotated(String s, String r) {
boolean result = false;

// No null strings or strings with different lengths
if ((s == null || r == null)
|| s.length() != r.length()) {

result = false;

} else {

// The case of equals strings (rotation == 0)
if (s.equalsIgnoreCase(r)) {
result = true;

} else {

// Take the first char of the original string.
char c = s.charAt(0);

// Find the first ocurrence of the char c on the rotated string
// but as the char could be repeated we need to find it
// from the right.
int i = -1;
for (int j = r.length() - 1; j != 0; j--) {
if (c == r.charAt(j)) {
i = j;
break;
}
}

if (i != -1) {
// Extract the 2 substrings
String s1 = r.substring(0, i);
String s2 = r.substring(i);

// Compare the original string with the
// concatenation of the 2 substrings, s2 and s1.
result = s.equals(s2 + s1);
}
}
}

return result;
}

Javin Paul said...

Great, you can also share the test you ran. I am thinking on this line now that to add some test code, normal Asset statements instead of printing. That helps to understand the logic better.

--j aneiros said...

Hello Javin,

The function was broken, the following test was not passing:

assertTrue(isRotated("abcade", "eabcad"));

/**
* Test of isRotated method, of class RotatedString.
*/
@Test
public void testIsRotated() {
System.out.println("isRotated");
assertTrue(isRotated("abc", "bca"));
assertTrue(isRotated("abc", "cab"));
assertFalse(isRotated("abc", "bac"));
assertFalse(isRotated("abc", null));
assertFalse(isRotated("abc", ""));

assertTrue(isRotated("1234", "2341"));
assertTrue(isRotated("1234", "3412"));
assertTrue(isRotated("1234", "4123"));
assertFalse(isRotated("1234", "23s41"));
assertFalse(isRotated("1234", null));
assertFalse(isRotated("1234", ""));

assertTrue(isRotated("abcda", "daabc"));
assertTrue(isRotated("abcde", "deabc"));
assertTrue(isRotated("abcade", "eabcad"));
assertTrue(isRotated("abcdea", "deaabc"));
assertTrue(isRotated("abcdea", "abcdea"));
assertTrue(isRotated("abcddeeaaa", "bcddeeaaaa"));
assertTrue(isRotated("abbcddeeaaa", "bcddeeaaaab"));
assertTrue(isRotated("abcadea", "adeaabc"));
assertTrue(isRotated("abcadea", "eaabcad"));
assertFalse(isRotated("abcdea", "dceaab"));
}

--j aneiros said...

This one passes all tests.

/**
* The function checks if a string is a rotation of another string. By
* rotation we understand the shifting of 1 or more characters without
* losing them, for example: daabc is a rotated string of abcda, deaabc is a
* rotation of abcdea and dceaab is not a rotation of abcdea.
*
* The fundamental idea behind this solution is that any rotated string is
* just the concatenation of 2 consecutive substrings that forms the
* original one, for example da and abc are 2 substrings from abcda, dea and
* abc are the 2 from abcdea.
*
* The function finds the 2 substrings, concatenates them and returns the
* result of the comparison with the original.
*
* The function handles null strings, different length strings and
* ignores case.
*
* @param s The original string
* @param r The rotated string
* @return A boolean
*/
public static boolean isRotated(String s, String r) {
boolean result = false;

// No null strings or strings with different lengths
if ((s == null || r == null)
|| s.length() != r.length()) {

result = false;

} else {

// Take the first char of the original string.
char c = s.charAt(0);

// Find the first ocurrence of the char c on the rotated string,
// extract 2 substrings and compare the concatenation with the
// original string.
for (int i = 0; i < r.length(); i++) {

if (c == r.charAt(i)) {

// Take substring from the begining of the string till
// the char before the ocurrence of c.
// This works because substring of same start and end
// index returns an empty string "".
String s1 = r.substring(0, i);

// Take the substring from c till the end of string.
String s2 = r.substring(i);

// Concatenate and compare.
if (s.equals(s2 + s1)) {
result = true;
break;
}
}
}
}

return result;
}

Javin Paul said...

Thanks a lot, make much more sense now.

Post a Comment