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

    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
        move += 1
    print(word[possibilities[0]:] + word[:possibilities[0]])

Test 1

Verdict: RUNTIME ERROR

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