Checking if strings are rotations of each other or not

Jan. 18, 2021 35019

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

String manipulation problems are one of the most frequently asked problems in Programming job interviews and today we are going to discuss one of these problems.
We are provided with two Strings and our task is to check whether the given Strings are rotations of each other or not. A String is said to be rotation of another String if :
• Both the Strings have equal lengths and consist of same characters.
• We can obtain the second string by rotating the first String around a certain character.

For example, Suppose we have two strings S1 = "HELLO", and S2 = "LOHEL". Both of them have equal lengths and have the same characters. By rotating "HELLO" three position to the left we can obtain "LOHEL". So, these Strings are rotation of each other.

​​Approach:

In order to solve this problem, we will firstly check if the Strings are of same length. After that we will concatenate the first string with itself, then check whether the second one is present in the concatenated string or not. This is because if you join a String with itself then it actually contains all rotated versions of itself

If the second String exists in the concatenated String, the Strings are rotations of each other. In our example, for S1="HELLO",  the concatenated String will be "HELLOHELLO". As we can see, this concatenated string contains the String "LOHEL" and thus, these Strings are rotations of each other.

Algorithm: checkRotation(s1,s2)

1. Check lengths of s1 and s2 and return false if they are not same.
2. If Strings are of equal length, store the concatenation of s1 with s1 itself in variable temp.
temp := st1+st1
3. Check if temp contains s2 then, return true otherwise return false.

Pseudocode:

​checkRotation(s1,s2)
if s1.length != s2.length
return False
else
temp = s1 + s1
if s2 in temp
return True
else
return False

Code:

• C/C++
• Java
• Python
#include<iostream>

using namespace std;

bool checkRotation(string s1, string s2) {
/* Comparing and checking string lengths */
if (s1.length() != s2.length())
return false; //returning false if strings are unequal

string temp = s1 + s1; //storing concatenated string

int n = temp.length();
int m = s2.length();

// checking if s2 is present in temp
for(int i = 0; i<n-m; i++)
{
int flag = 1, j;
for(j = 0; j < m-1; j++)
{
if(s2[j] != temp[i+j])
{
flag = 0;
break;
}
}

if(flag == 1){
return true;// return true if s2 is present in temp
}
}

return false;
}

/* Driver code */
int main() {
string a = "HELLO", b = "LOHEL";
if (checkRotation(a, b))
cout<<"Given Strings are rotations of each other.";
else
cout<<"Given Strings are not rotations of each other.";
return 0;
}

class StrRotation {
static boolean checkRotation(String s1, String s2) {
/* Comparing and checking string lengths */
if (s1.length() != s2.length())
return false;

String temp = s1 + s1; //storing concatenated string

if (temp.indexOf(s2) != -1) {
return true; //returning true if 2nd string is present in concatenated string
} else {
return false;
}

}

// Driver code
public static void main(String[] args) {
String a = "HELLO";
String b = "LOHEL";

if (checkRotation(a, b))
System.out.println("Given Strings are rotations of each other.");
else
System.out.println("Given Strings are not rotations of each other.");
}
}

def checkRotation(s1, s2):
temp = ''

# Check if lengths of two strings are equal or not
if len(s1) != len(s2):
return False

# storing concatenated string
temp = s1 + s1

if s2 in temp:
return True #returning true if 2nd string is present in concatenated string
else:
return False

# Driver program to test the above function
string1 = "HELLO"
string2 = "LOHEL"

if checkRotation(string1, string2):
print("Given Strings are rotations of each other.")
else:
print("Given Strings are not rotations of each other.")


Output:

Given Strings are rotations of each other.

Complexity Analysis:

The time complexity depends on the process of finding the string S2 in the concatenated string. We can see that the outer loop runs from 0 to n-m and inner loop runs from 0 to m-1 where n is the length of the concatenated string and m is the length of string we want to check. For each iteration of the outer loop, the inner loop will run m-1 times, therefore the loop will execute for n-m*(m-1).
Thus, the final time complexity comes out to be O(m*n). The space complexity for this problem is O(1).

In this way we can check if two given Strings are rotations of each other or not.

Liked the post?
Zealous Learner.
Editor's Picks
0 COMMENT