MINMOVE - Minimum Rotations
| English | Vietnamese |
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.
Input
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.
Output
A single line contains an integer which represents the minimum number of rotations.
Example
Input: mississippi Output: 10
Test cases and time limit have been updated. Some accepted solution got TLE.
hide comments
|
rising_stark:
2024-06-30 16:25:59
@coolcoder_iith How did you know it timed out at 12?
|
|
coolcoder_iith:
2019-10-03 20:19:13
time out at #12
|
|
yaswanth:
2019-09-15 17:47:12
Tried n*logn*logn with quite number of optimisations. TLE
|
|
inkretbear:
2018-08-23 23:15:18
Was getting WA on #17 with prefix hash
|
|
hamjosh1:
2016-09-30 13:29:49
learned a lot :D |
|
vsp4:
2016-09-11 19:19:06
Those who are using stl, make sure to use stable_sort if using nlogn*logn solution. Costed me few WA |
|
minhthai:
2016-04-03 05:42:51
"Some accepted solution got TLE."
|
|
lakshay_v06:
2016-02-05 15:33:28
Same as http://www.spoj.com/problems/BEADS/ . O(nlogn) passed. :) |
|
Dhawal Harkawat:
2016-01-22 05:30:20
silly mistake costed two WAs at #10. finally AC. |
|
Sumit Vohra:
2016-01-21 23:37:21
solved using suffix automaton in O(n)
|
| Added by: | Race with time |
| Date: | 2008-12-29 |
| Time limit: | 0.100s |
| Source limit: | 50000B |
| Memory limit: | 1536MB |
| Cluster: | Cube (Intel G860) |
| Languages: | All except: ERL JS-RHINO PERL6 |
| Resource: | Based on a problem from ACM Central European Programming Contest |
RSS