Check if given string can be derived from another string by circularly rotating it. The rotation can be in clockwise or anti-clockwise rotation.
X = ABCD
Y = DABC
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.
C++ implementation –
using namespace std;
// Function to check if X can be derived from Y by rotating it
bool check(string X, string Y)
// if string lengths are different, they can't be
// derived from each other
if ((m = X.length()) != Y.length())
// Invariant : At i'th iteration of this loop,
// string X will be rotated by i units
for (int i = 0; i < m; i++)
// in-place left rotate string X by 1 unit
rotate(X.begin(), X.begin() + 1, X.end());
// for right rotation, we can use reverse iterators.
// i.e. rotate(X.rbegin(), X.rbegin() + 1, X.rend());
// return true if X becomes equal to Y
// return false if no rotation is matched
// main function
string X = "ABCD";
string Y = "DABC";
if (check(X, Y))
cout << "Given strings can be derived from each other";
cout << "Given strings cannot be derived from each other";
Given strings are rotation of each other
Thanks for reading.