Problem statement

https://leetcode.com/problems/orderly-queue/

Solution

If K > 1 than we can change any two adjacent elements: first we can rotate our string, such that we have abX, where X is some string. Then we can put b to the end and then a to the end, rotate again and we have baX. Now we can look at it as an bubble sort: doing these moves we can sort all string. If K = 1 we allowed only rotate string and goal is to choose smallest one among n options.

Complexity

Time complexity is O(n^2) for time and O(n) for space

Code

class Solution:
    def orderlyQueue(self, S, K):
        if K > 1: return "".join(sorted(S))
        return min(S[i:]+S[:i] for i in range(len(S)))

Remark

There is also O(n) Booth’s Algorithm for finding of minimal rotation. Using count sort we can make whole algorithm O(n). However given restrictions it is not needed.