Rotations

import sys

def get_next_index(move, i, n):
    if i + move < n:
        return i + move
    else:
        return move + i - n


if __name__ == '__main__':
    word = sys.stdin.readline().strip()
    N = len(word)
    index = list(range(N))

    sorted_letters, index = zip(*sorted(zip(word, index)))
    start_letter = list(sorted_letters[0])

    possibilities = list()

    for i in range(len(sorted_letters)):
        if start_letter[0] == sorted_letters[i]:
            possibilities.append(index[i])
        else:
            break

    if len(possibilities) == N:
        print(word)
    else:
        move = 1
        while(len(possibilities)) > 1 and move < N:
            letters = list()
            for start_index in possibilities:
                letters.append(word[get_next_index(move, start_index, N)])

            sorted_next_letters, new_possibilities = zip(*sorted(zip(letters, possibilities)))
            i = 0
            possibilities = list()
            while i < len(sorted_next_letters) and sorted_next_letters[0] == sorted_next_letters[i]:
                possibilities.append(new_possibilities[i])
                i += 1
            if len(possibilities) >= N - move:
                break
            move += 1

        if possibilities[0] is 0:
            print(word)
        else:
            print(word[possibilities[0]:] + word[:possibilities[0]])

Test 1

Verdict: ACCEPTED

Test 2

Verdict: ACCEPTED

Test 3

Verdict: ACCEPTED

Test 4

Verdict: ACCEPTED

Test 5

Verdict: TIME LIMIT EXCEEDED

Test 6

Verdict: TIME LIMIT EXCEEDED

Test 7

Verdict: TIME LIMIT EXCEEDED

Test 8

Verdict: ACCEPTED

Test 9

Verdict: ACCEPTED

Test 10

Verdict: ACCEPTED

Test 11

Verdict: ACCEPTED

Test 12

Verdict: TIME LIMIT EXCEEDED