SP3605 MINMOVE - Minimum Rotations

[English](/problems/MINMOVE/en/) [Vietnamese](/problems/MINMOVE/vn/)Given a string S\[1..n\] . A rotation on S is that we move the first character to the right-most of the string. More specific, after a rotation, S becomes T = S\[2..n\] + S\[1\]. For example: S = abcaa, then after a rotation we have S = bcaaa. Find the minimum number of rotations to make S become the smallest lexicographical order string.

A single line contains a string S. S contains only small letters of English alphabet (‘a’ .. ‘z’), and the length of S is not more than 100000.

A single line contains an integer which represents the minimum number of rotations.