Check if strings can be derived from each other by circularly rotating them

Check if given string can be derived from another string by circularly rotating it. The rotation can be in clockwise or anti-clockwise rotation.


For example,



Output: Yes

Y can be derived from X by right-rotating string X by 1 unit



For two given strings X and Y, a simple solution would be to check if string Y is sub-string of string XX or not. If yes, they can be derived from each other. For example, consider string X = ABCD and Y = DABC


string Y is clearly a substring of ABCDABCD

The implementation can be seen here. This solution seems efficient but it is using O(n) extra space.

How to do this using O(1) space ?
The idea is to in-place rotate the string X and check if it becomes equal to string Y or not. We have to consider every possible rotation of string X (i.e. rotation by 1 unit, 2 unit.. till n-1 unit where n is the length of string X). Note that clockwise or anti-clockwise rotation doesn’t matter.

C++ implementation –

Download   Run Code


Given strings are rotation of each other


Thanks for reading.

Please use ideone or C++ Shell or any other online compiler link to post code in comments.
Like us? Please spread the word and help us grow. Happy coding 🙂