Solution
Approach 1: Mathematical
Intuition
Call the move that takes the K
th letter from the beginning and puts it on the end, a "K
kick" move.
Examining 1kick moves, they let us consider the string as a "necklace" that may be rotated freely, where each bead of the necklace corresponds to a letter in the string. (Formally, this is the equivalence class under 1kick moves.)
Examining 2kick moves (in the context of treating the string as a necklace), they allow us to swap the positions of two adjacent beads. Thus, with 2kick moves, every permutation of necklace is possible. (To actually construct the necklace, we bring the second smallest bead to be after the smallest, then the third smallest to be after the second smallest, and so on.)
The previous insight may be difficult to find. Another strategy is to write a brute force program to examine the result of 2kick moves  then we might notice that 2kick moves allow any permutation of the string.
Yet another strategy might be to explicitly construct new moves based on previous moves. If we perform a 2 kick move followed by many 1 kick moves, we can move a string like "xyzzzzzz" > "xzzzzzzy" > "yxzzzzzz"
, proving we can swap the positions of any two adjacent letters.
Algorithm
If K = 1
, only rotations of S
are possible, and the answer is the smallest rotation.
If K > 1
, any permutation of S
is possible, and the answer is the letters of S
written in lexicographic order.
Complexity Analysis

Time Complexity: , where is the length of
S
. 
Space Complexity: .
Analysis written by: @awice.