Check if a string is rotation of another string in C++

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

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.