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)))

    pos_count = 0
    for i in range(N):
        if sorted_letters[0] == sorted_letters[i]:
            pos_count += 1
        else:
            break

    possibilities = index[:pos_count]

    if len(possibilities) == N:
        print(word)
    else:
        move = 1
        while(len(possibilities)) > 1 and move < N:
            letters = len(possibilities) * [0]
            i = 0
            for start_index in possibilities:
                letters[i] = word[get_next_index(move, start_index, N)]
                i+=1

            sorted_next_letters, new_possibilities = zip(*sorted(zip(letters, possibilities)))

            pos_count = 0
            for i in range(len(sorted_next_letters)):
                if sorted_next_letters[0] == sorted_next_letters[i]:
                    pos_count += 1
                else:
                    break
            possibilities = new_possibilities[:pos_count]

            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