899. Orderly Queue
龍大拿到了一組字串，他每次可以從前 k 個字元挑一個移到字串末，並且可以操作無限次
龍大希望這個字串的字典序越小越好，如果太大的話可能會有人一直討論他
為了龍大的心理健康，請你幫他找出這個最小字典序的字串。
Example 1:
Input: s = "cba", k = 1
Output: "acb"
可以由 cba->bac->acb 得到
Example 2:
Input: s = "baaca", k = 3
Output: "aaabc"
可以由 baaca->aacab->aaabc 得到
思路:
1.先從簡單版本開始想 如果 k=1 每次只能換第一個字元 可能性就只有 len(s) 種
就掃一次看誰最小就好
2.如果 k=2 可能性就多很多了 因為操作不限次數 可以想一下操作可以做到什麼地步?
有沒有辦法只交換任意相鄰兩個字元的位置 如果可以其實就能 bubble sort
考慮 1234ab5678 如果要交換 ab
可以先把1234依序換到最後: ab56781234
接著換 a56781234b -> 56781234ba -> 1234ba5678
所以 k=2 就足以交換任意相鄰字元的位置 也等同於能做到任意排列
最小的字典序字串只要直接 sort 就能得到
3.Python code:
class Solution:
def orderlyQueue(self, s: str, k: int) -> str:
if k > 1:
return ''.join(sorted(s))
return min([s[i:]+s[:i] for i in range(len(s))])