Strings Rotations of Each Other

You are given two strings of equal lengths, s1 and s2. The task is to check if s2 is a rotated version of the string s1.

Note: The characters in the strings are in lowercase.

Examples :

Input: s1 = "abcd", s2 = "cdab"
Output: true
Explanation: After 2 right rotations, s1 will become equal to s2.

Input: s1 = "aab", s2 = "aba"
Output: true
Explanation: After 1 left rotation, s1 will become equal to s2.

Input: s1 = "abcd", s2 = "acbd"
Output: false
Explanation: Strings are not rotations of each other.

Constraints:
1 <= s1.size(), s2.size() <= 10⁵

Approach 01:

#include <string>

class Solution {
public:
    // Function to check if two strings are rotations of each other or not.
    bool areRotations(const std::string &string1, const std::string &string2) {
        std::string concatenatedString = string1 + string1;
        return concatenatedString.find(string2) != std::string::npos;
    }
};

class Solution:
    def areRotations(self, string1: str, string2: str) -> bool:
        concatenatedString = string1 + string1
        if string2 in concatenatedString:
            return True
        return False

Time Complexity

• Concatenation of the string:

  The concatenation of string1 with itself creates a string of length \(2N\), where \(N\) is the length of string1. This operation takes \(O(N)\).

• Finding string2 in the concatenated string:

  The find function searches for string2 in the concatenated string. This takes \(O(2N)\) in the worst case, where \(M\) (the length of string2) equals \(N\).

• Overall Time Complexity:

  The overall time complexity is \(O(N + 2N) = O(N)\), as the dominant term is linear with respect to \(N\).

Space Complexity

• Concatenated string:

  The concatenated string concatenatedString is of size \(2N\), requiring \(O(2N)\) space.

• Input strings:

  Both string1 and string2 are part of the input, so their space is not counted as additional.

• Overall Space Complexity:

  The overall space complexity is \(O(N)\), as \(2N\) simplifies to \(O(N)\).