PROBLEM LINKS
DIFFICULTY
MEDIUM
EXPLANATION
We are given a string S and we keep rotating it till we get back to the string S. Note that this can always be possible, if we rotate S a multiple of N times, where N is the length of S. But, we are more concerned if it can be reached before that. Let S(i) = S[i…N-1] + S[1…i-1]. So S(0) = S. Once we know for each i, if S(i) equals S, then we can simulate the rotations of Monkey and Po, as any rotation will result in a string which is one of S(i). We can use KMP here :). Consider a string S2 = S + S and find the KMP Failure Function F for S2. F[i] denotes the length of the maximum proper-suffix that is also prefix of S2.
If F[i] = N, then N length suffix of S2[0,…,i], i.e., S2[i-N+1,…,i] = N length prefix of S2[0,…,i] = S2[0…N-1] = S. So, we can find all such indices using O(n) KMP and then just simulate the rotations by just going through the S(i)s in order. Note that answer will always exist and there is never a -1 case.
SETTER’S SOLUTION
Can be found here.
TESTER’S SOLUTION
Can be found here.