String Rotation in Java - How to check if strings are rotations of each other or not

String-based algorithmic questions are very popular in Java interviews e.g. checking if two String is the anagram of each other (see), or checking if given String is a palindrome (see), or just finding permutations of given String (see). One of such popular String-based interview questions is about to check if two Strings are a rotation of each other in Java. In order to solve this question, you should know what is String rotation? Well, A string is made of characters and you just rotate the String around any character like "programming" will become "ingprogramm" if we rotate the String on trailing character 3 times.

A k-rotation on a string takes the trailing k characters of the string and attaches it to the beginning of the string in the same order.

You can rotate the String either in the clockwise (right from the top) or anti-clockwise(left from the top). The string can also be rotated in one go like "123456" will become "456123" if we rotate 456 to the left around character "3".


Problem: 
Write a program to check if two given String s1 and s2 are rotations of another. For example if s1 = "IndiaUSAEngland" and s2= "USAEnglandIndia" then your program should return true but if s2="IndiaEnglandUSA" then it should return false.

For the purpose of this program, you can assume that Strings are rotated on the right side, but you should ask this question to your interviewer before jumping into the solution. Paying attention to such details score brownie points on real Interview.

Remember, attention to details is one of the desired quality for software engineers. Also, a basic knowledge of common data structure like String is mandatory and you should spend some time brushing up your DSA skills. If you need a resource, I highly recommend the Data Structures and Algorithms: Deep Dive Using Java course by Tim Buchalaka on Udemy. It's a great course to brush up your coding skills as well. 




How to check if strings are rotations of each other or not

The simplest solution to this complex problem is to concatenate the String with itself and check if the given rotation exists in this concatenated String. If it exists then the second string is a rotation of the first string.

Btw, before concatenating String, you should also first check the length of the two String. If they are of a different length than two strings are definitely not the rotation of each other, but if they have the same length then you need to check further.

This will result in faster solutions because checking length is faster than checking if a substring exists in the given String.

Here is the exact algorithm to check if a given String is a rotation of another:

1) check the length of two strings, if the length is not same then return false
2) concatenate given string to itself
3) check if the rotated version of String exists in this concatenated string
4) if yes, then the second String is rotated version of the first string

This kind of little tricks really helps to solve coding problems during programming job interviews and in your day-to-day life. If you want to learn more of such patterns to boost your problem-solving skills then I also recommend you check out Grokking the Coding Interview: Patterns for Coding Questions course on Educative.

This will also help you to improve your coding sense by developing pattern recognition and art of developing a bigger unknown problem into smaller known ones.

Anyway, here is the logic to check if two strings are rotation of each other in code:

String Rotation in Java - Write a Program to check if strings are rotations of each other or not



Java Program to check if One String Rotation of Another

And, here is our complete Java program to check if a given string is the rotation of another given String or not.

import java.util.Scanner;

/*
 * Java Program to check if one String is rotation of
 * another.
 */
public class Main {

  public static void main(String[] args) throws Exception {

    Scanner scnr = new Scanner(System.in);
    System.out.println("Please enter original String");
    String input = scnr.nextLine();

    System.out.println("Please enter rotation of String");
    String rotation = scnr.nextLine();

    if (checkRotatation(input, rotation)) {
      System.out.println(input + " and " + rotation
          + " are rotation of each other");
    } else {
      System.out.println("Sorry, they are not rotation of another");
    }

    scnr.close();
  }

  /**
   * This method check is given strings are rotation of each other
   * @param original
   * @param rotation
   * @return true or false
   */
  public static boolean checkRotatation(String original, String rotation) {
    if (original.length() != rotation.length()) {
      return false;
    }

    String concatenated = original + original;

    if (concatenated.indexOf(rotation) != -1) {
      return true;
    }

    return false;
  }
}


Output
Please enter original String
IndiaVsAustralia
Please enter rotation of String
AustraliaVsIndia
Sorry, they are not the rotation of another

Please enter original String
IndiaVsEngland
Please enter rotation of String
EnglandIndiaVs
IndiaVsEngland and EnglandIndiaVs are rotation of each other

You can see that when a user enters "IndiaVsAustralia" and "AustraliaVsIndia" then our program return false because they are not a rotation of each other, but, when the user enters "IndiaVsEngland" and "EnglandIndiaVs" then our program returns true because here two strings are the rotation of each other.

That's all about how to check if one String is a rotation of another in Java. As I said, the simplest way to solve this problem is to concatenate String with itself and check if rotation exists in the concatenated String or not. If it exists, it means they are a rotation of each other. If not, the first string is not a rotation of other.

Though, there are a couple of variants of this program that many interviewers ask as follow-ups e.g. how do you solve the problem if strings are rotated on the left side, or can you check if two strings are the rotation of another without using String concatenation. You can try solving those versions by yourself, but if you want to look for a solution, you can check it here.

Further Learning
The Coding Interview Bootcamp: Algorithms + Data Structures
Data Structures and Algorithms: Deep Dive Using Java
Cracking the Coding Interview - 189 Questions and Solutions
Algorithms and Data Structures - Part 1 and 2
Grokking the Coding Interview: Patterns for Coding Questions


Related String-based Algorithmic Questions from Interviews, you may like to practice:
  • How to Print duplicate characters from String? (solution)
  • How to find duplicate characters in a String? (solution)
  • 10 Algorithm books Every Programmer Should Read (list)
  • 5 Books to learn data structure and algorithms in Java? (books)
  • How to check if String is Palindrome? (solution)
  • 10 Algorithms Books Every Programmer Should Read (books)
  • Top 50 Java Programs from Coding Interviews (see here)
  • How to return the highest occurred character in a String? (solution)
  • How to check if a string contains only digits?  (solution)
  • How to reverse String in Java using Iteration and Recursion? (solution)
  • 100+ Data Structure Coding Problems from Interviews (questions)
  • How to count the number of vowels and consonants in a String? (solution)
  • Top 20 String coding interview questions (see here)
  • How to program to print the first non-repeated character from String? (solution)
  • 10 Free Data Structure and Algorithm Courses for Programmers (courses)
  • How to count the occurrence of a given character in String? (solution)
  • 5 Free Data Structure and Algorithms Courses for Programmers (courses)
  • How to convert numeric String to an int? (solution)
  • How to reverse words in a sentence without using a library method? (solution)
  • How to reverse a String in place in Java? (solution)
  • 50+ Data Structure and Algorithms Problems from Interviews (questions)

Thanks for reading this article so far. If you like this interview question then please share it with your friends and colleagues.

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. 

5 comments:

  1. /**
    * Author : Anil Churasiya
    * email : achaurasiya59@gmail.com
    * Date : October 12, 2018
    */
    import java.util.Scanner;

    class StringRotation{
    public static void main(String[] args) {
    Scanner sc = new Scanner(System.in);
    String str1 = sc.nextLine();
    String str2 = sc.nextLine();
    boolean status = isRotated(str1, str2);
    if(status){
    System.out.println("True");
    }
    else{
    System.out.println("False");
    }
    }

    public static boolean isRotated(String str1, String str2){
    boolean status = false;
    char arrStr1[] = str1.toCharArray();
    char arrStr2[] = str2.toCharArray();
    if(arrStr2.length != arrStr1.length){
    return false;
    }
    char temp;
    for(int i=0; i<arrStr2.length-1; i++){
    int len = 0;
    String tempString = "";
    temp = arrStr2[0];
    while(len<arrStr2.length-1){
    arrStr2[len] = arrStr2[len+1];
    len++;
    }
    arrStr2[len] = temp;
    for(int j=0; j<arrStr2.length; j++){
    tempString = tempString + arrStr2[j];
    }
    if(str1.equals(tempString)){
    status = true;
    return status;
    }
    }
    return status;
    }
    }

    ReplyDelete
  2. /**
    * Author : Artem Lavrinenko
    * email : lavrinenkoag@gmail.com
    * Date : December 11, 2018
    */

    public class Main {
    public static boolean isRotated (String line1, String line2) {
    if (line1.length() != line2.length())
    return false;

    for (int s = 0, e = line2.length() - 1; s < line1.length() && e >= 0; s++, e--) {
    if (line1.charAt(s) != line2.charAt(e)) {
    return false;
    }
    }
    return true;
    }

    public static String rotateString (String line) {
    char[] arrLine = line.toCharArray();
    for (int s = 0, e = arrLine.length - 1; s <= arrLine.length / 2 && e >= arrLine.length / 2; s++, e--) {
    char c = arrLine[s];
    arrLine[s] = arrLine[e];
    arrLine[e] = c;
    }
    return String.valueOf(arrLine);
    }

    public static void main(String[] args) {
    System.out.println("0123 and 3210: " + isRotated("0123", "3210"));
    System.out.println("0123 and 0123: " + isRotated("0123", "0123"));
    System.out.println("0123456789 - " + rotateString("0123456789"));
    }
    }


    0123 and 3210: true
    0123 and 0123: false
    0123456789 - 9876543210

    ReplyDelete
  3. import java.util.*;
    public class HelloWorld{

    public static void main(String []args)
    {


    String s="IndiaVsAustralia";
    String s1="AustraliaVsIndia";
    String s2=s+s;
    int n=s2.length();
    int n1=n/2;
    System.out.println(n+""+n1);
    System.out.println(s2);
    String s4=s2.substring(n1/2,(n-(n1/2)));
    System.out.println(s4);
    if(s4.equals(s1)){
    System.out.println("Treu");

    }
    else
    {
    System.out.println("False");
    }
    }
    }









    ReplyDelete
  4. My solution in Javascript(This is working for string only not for numbers)

    function match(str1, str2) {
    var count = str2[0];
    debugger;
    if(str1.length !== str2.length) {
    return false
    } else {
    for(var i = 1; i <= str2.length; i++) {
    if(str2[i].charCodeAt() >= 97 && str2[i].charCodeAt() <= 122) {
    count = count.concat(str2[i]);
    } else {
    break;
    }
    }
    }

    if(str1.includes(count)) {
    var sub = str2.substr(count.length);
    var newSub = sub.concat(count);
    for(var j = 0; j <= str1.length - 1; j++) {
    if(str1[j] === newSub[j]) {
    continue
    } else {
    return false
    }
    }
    } else {
    return false
    }

    return true
    }

    match("KanchanTyagi", "TyagiKanchan")

    ReplyDelete