In this article, we will dicuss different ways to check if a string is a rotation of another string in C++.

**Table Of Contents**

## Problem Description

We have been given with two strings . Now, we have to check if a string is a rotation of the other string .

A String is rotation of another String if :-

1. Both the Strings have equal size and have similar characters.

2. By turning the first String around a specific character, we can get the second string.

Let’s see some examples of these strings,

**Input**

**Advertisements**

s1 = "QWERTY" s2 = "TYQWER"

**Output**

Strings are rotations of each other

**Input**

s1 = "QWERTY" s2 = "QWRETY"

**Output**

Strings are not rotations of each other

The solution can be acheived by following approaches.

## Method 1: Brute Force

Suppose if we rotate s1 by k. Then, instead of s1[0], s1[1], s1[2], …, we have s1[k], s1[k+1], s1[k+2], …; and so we should check that s1[k] == s2[0], s1[k+1] == s2[1], s1[k+2] == s2[2], etc.

`Time Complexity: O(n*n) , where n1 and n2 are the length of the strings`

`Space Complexity: O(1)`

#include <bits/stdc++.h> using namespace std; bool checkRotation(string s1, string s2) { //If the length of both the strings are not equal then returning false if(s1.size()!=s2.size()) { return false; } int n = s1.size(); // checking from which index the string has rotated and from that //index checking whether all the elements are at their correct position for(int i=0;i<n;i++) { int j=0; while(j<n && s1[(i+j)%n] == s2[j]) { j++; } if(j==n) { return true; } } return false; } int main() { // initialising strings string s1 = "QWERTY", s2 = "TYQWER"; // calling function and printing result according to what the function returns if (checkRotation(s1, s2)) cout << "Strings are rotations of each other" << endl; else cout << "Strings are not rotations of each other" << endl; // initialising strings s1 = "QWERTY"; s2 = "QWRETY"; // calling function and printing result according to what the function returns if (checkRotation(s1, s2)) cout << "Strings are rotations of each other" << endl; else cout << "Strings are not rotations of each other" << endl; return 0; }

**Output**

Strings are rotations of each other Strings are not rotations of each other

## Method 2: Using concatination

Second approach is to store the concatenation of string 1 to string 1 in a new string. If string 2 is a substring of the concatenated string, then string 1 and string 2 are rotation of each other

`Time Complexity: O(n*n), where n is the length of the string`

`Space Complexity: O(n)`

# include <iostream> using namespace std; bool checkRotations(string s1, string s2) { //If the length of both the strings are not equal then returning false if (s1.length() != s2.length()) return false; //concatenate string 1 with string 1 string temp = s1 + s1; //checking whether string 2 is present in concatenated string return (temp.find(s2) != string::npos); } int main() { // initialising strings string s1 = "QWERTY", s2 = "TYQWER"; // calling function and printing result according to what the function returns if (checkRotations(s1, s2)) cout << "Strings are rotations of each other" << endl; else cout << "Strings are not rotations of each other" << endl; // initialising strings s1="QWERTY"; s2="QWRETY"; // calling function and printing result according to what the function returns if (checkRotations(s1, s2)) cout << "Strings are rotations of each other" << endl; else cout << "Strings are not rotations of each other" << endl; return 0; }

**Output**

Strings are rotations of each other Strings are not rotations of each other

## Method 3: Using queues

**Algorithm of this approach :-**

If the length of both the strings are not equal, then it can never be possible. Now we have to push the characters of original string in queue q1. Push the characters of string which is to be checked inside another queue q2. Now we have to keep popping characters from queue q2 and than also pushing it back into it untill the number of such operations are less than the size of the given string. If q2 becomes equal to q1 at any time throughout these operations, it is possible otherwise it is not possible.

`Time Complexity: O(n1 + n2) , where n1 and n2 are the length of the strings`

`Space Complexity: O(n)`

#include <iostream> #include <queue> using namespace std; bool checkRotation(string s1, string s2) { //If the length of both the strings are not equal then returning false if (s1.size() != s2.size()) { return false; } queue<char> q1,q2; // pushing characters of string s1 into queue q1 for (int i = 0; i < s1.size(); i++) { q1.push(s1[i]); } // pushing characters of string s2 into queue q2 for (int i = 0; i < s2.size(); i++) { q2.push(s2[i]); } int cnt = s2.size(); // popping characters from q2 and pushing it back again until k is greater than 0 while (cnt--) { char ch = q2.front(); q2.pop(); q2.push(ch); if (q2 == q1) { return true; } } return false; } int main() { // initialising strings string s1 = "QWERTY", s2 = "TYQWER"; // calling function and printing result according to what the function returns if (checkRotation(s1, s2)) cout << "Strings are rotations of each other" << endl; else cout << "Strings are not rotations of each other" << endl; // initialising strings s1 = "QWERTY"; s2 = "QWRETY"; // calling function and printing result according to what the function returns if (checkRotation(s1, s2)) cout << "Strings are rotations of each other" << endl; else cout << "Strings are not rotations of each other" << endl; return 0; }

**Output**

Strings are rotations of each other Strings are not rotations of each other

## Summary

In this article we have seen various methods to check if a string is a rotation of the other string . We also got to know the time complexity of each of the methods and how each method is used for checking if a string is rotation of another string. Thanks.

**Advertisements**

Thanks for reading.