Check If One String Is A Rotation Of Another String

Moderate
0/80
Average time to solve is 15m
profile
Contributed by
121 upvotes
Asked in companies
AmazonAmerican ExpressSAP Labs

Problem statement

You are given two Strings 'P' and 'Q' of equal length.


Your task is to return 1 if String 'P' can be converted into String 'Q' by cyclically rotating it to the right any number of times ( Possibly Zero ), else return 0.


A cyclic rotation to the right on String 'A' consists of taking String 'A' and moving the rightmost character to the leftmost position. For example, if 'A' = "pqrst", then it will be "tpqrs" after one cyclic rotation on 'A'.


For example: 
Consider the two strings 'P' = "abfyg" and 'Q' = "gabfy" 

If we cyclically rotate String 'P' to the right once. The resulting string P becomes "gabfy" which is equal to String 'Q'. 

Therefore it is possible to convert String 'P' to String 'Q'.
Detailed explanation ( Input/output format, Notes, Images )
Input Format: 
The first line contains the String 'P'.
The second line contains the String 'Q'.
Output Format: 
The only line contains 1 if String 'P' can be converted to String 'Q' by cyclically rotating it to the right any number of times, otherwise 0.
Note: 
You do not need to print anything, it has already been taken care of. Just implement the given function.
Sample Input 1:
abac
baca
Sample Output 1:
1
Explanation For Sample Input 1:
Let's try rotating the String 'P' to the right and try all the possible rotations:

1) If we rotate "abac" to the right, the resulting string becomes "caba".

2) If we rotate "caba" to the right, the resulting string becomes "acab".

3) If we rotate "acab" to the right, the resulting string becomes "baca" which is equal to String 'Q'.

Therefore it is possible to convert String 'P' to String 'Q'. Hence, we will return 1 in this case.
Sample Input 2:
aabca
bacaa
Sample Output 2:
0
Constraints:
1 <= |P| , |Q| <= 10^5
|P| = |Q|

String 'P' and 'Q' have the same length and contain only lowercase English letters.

Time Limit: 1 sec
Follow Up:
Can you solve this in O(N) time?
Hint

Try to generate all the cyclic rotations of the first string and compare them with the second string.

Approaches (2)
Brute Force Approach

The idea is to generate all the possible rotations of String P and compare each of them with String Q. To generate the next cyclic rotation of a string P from the current rotation we can move the last character of it to the first position while keeping the other characters unchanged.

 

This approach uses linear extra space but there is a way by which we can optimize the above method by which it will take constant extra space.

 

Let's take the String A = "abcd" having length N = 4.

  1. After 1 cyclic rotation, A becomes  "dabc".
  2. After 2 cyclic rotations, A becomes "cdab".
  3. After 3 cyclic rotations, A becomes "bcda".
  4. After 4 cyclic rotations, A becomes "dabc".
  5. After 5 cyclic rotations, A becomes "cdab".
  6. After 6 cyclic rotations, A becomes "bcda".

 

Consider the above example, from which we can observe that the Jth character of the string which is formed by cyclically rotating String A I times is the (I+J)%(N)th character of the original string A having length 'N'. 

Using this observation we can generate all the rotations without actually having to generate them thereby using constant extra spaces.

 

From the above example we can also conclude that for a string of length ‘N’ there are only N possible rotations as when the Nth rotation is performed the resulting string becomes equal to the original string and hence no more new rotations can be generated.

 

Steps :

 

  • Let N be the length of both the Strings P and Q.
  • Iterate from j = 0 to N-1
    • Define a flag variable isRotationPossible which will store whether the current rotation of string P is equal to String Q or not.
    • Iterate from i = 0 to N-1
      • If P[(i+j)%N] is not equal to Q[i] then set isRotationPossible to 0 and break the loop.
    • If isRotationPossible is equal to 1 then return 1 otherwise move to the next iteration.
  • If the process has not returned any value till now then we will return 0 as we were unable to right rotate the string P to make it equal to string Q.
Time Complexity

O(N ^ 2), where 'N' denotes the length of the two strings 'P' and 'Q'.

 

In the worst case, when String P is not a rotation of String Q, we will need to check for all N possible rotations of String P and it takes O(N) time to check for each rotation. Hence, the overall Time Complexity is O(N ^ 2).

Space Complexity

O(1).

 

We are using constant extra space only. Hence, the overall Space Complexity is O(1).

Code Solution
(100% EXP penalty)
Check If One String Is A Rotation Of Another String
Full screen
Console