# 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,

Input:
X = ABCD
Y = DABC

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

XX = ABCD + ABCD = ABCDABCD

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.

Below is C++ and Java implementation of the idea –

## Java

Output:

Given strings can be derived from each other

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 🙂

Get great deals at Amazon

In the for loop, I think it should be `rotate(X.begin(), X.begin()+I, X.end())` since we are checking for each rotation.