stringalgorithmstring-algorithm

Proof for minimum number of String Rotation Problem

Let's say we are rotating a string one at a time ("abcd" -> "bcda"). After some t rotations we get the same string. Let t be the minimum such number of rotations.

For ex:

  1. For S = "aaaa", t = 1
  2. For S = "abcabc", t = 3
  3. For S = "abcdef", t = 6

Now my question is, can there be any string for which this condition holds : t > len(S)/2 and t < len(S)? If not can you please explain why?

Solution

  • Let's assume you can rotate your string t times and it will be the same string. Then if you rotate it another len(S)-t times you will definitely get the same string. If we assume that t>len(S)/2 we straightforwardly get that len(S)-t<len(S)/2, so minimal rotation is always <=len(S)/2