难度: Hard
给定一个字符串 s 和一个整数 k 。你可以从 s 的前 k 个字母中选择一个，并把它加到字符串的末尾。
返回 在应用上述步骤的任意数量的移动后，字典序最小的字符串 。
示例 1：
输入：s = "cba", k = 1 输出："acb" 解释： 在第一步中，我们将第一个字符（“c”）移动到最后，获得字符串 “bac”。 在第二步中，我们将第一个字符（“b”）移动到最后，获得最终结果 “acb”。
示例 2：
输入：s = "baaca", k = 3 输出："aaabc" 解释： 在第一步中，我们将第一个字符（“b”）移动到最后，获得字符串 “aacab”。 在第二步中，我们将第三个字符（“c”）移动到最后，获得最终结果 “aaabc”。
提示：
1 <= k <= S.length <= 1000s 只由小写字母组成。运行时间: 26 ms
内存: 16.9 MB
class Solution:
def orderlyQueue(self, s: str, k: int) -> str:
n = len(s)
if k == 1:
a = []
for i in range(n):
a.append(s)
s = s[1:] + s[0]
a.sort()
return a[0]
else:
cur = list(s)
cur.sort()
ans = "".join(cur)
return ans
这个题解的思路是分两种情况讨论： 1. 当k=1时，我们只能选择队列的第一个字符，然后将其移到队列的末尾。这等价于对字符串进行旋转操作。我们将字符串s所有可能的旋转形式存储在数组a中，然后对数组a进行排序，取排序后的第一个字符串即为最优解。 2. 当k>1时，因为我们可以选择前k个字符中的任意一个，相当于可以对前k个字符进行任意排列。所以无论我们进行多少次操作，最终得到的字符串在字典序上一定不会小于将原字符串按字典序排列得到的字符串。所以我们直接对原字符串的字符进行排序即可得到最优解。
时间复杂度: O(n^2)
空间复杂度: O(n^2)
class Solution:
def orderlyQueue(self, s: str, k: int) -> str:
n = len(s)
if k == 1:
# 当k=1时，将所有旋转后的字符串存入数组a中
a = []
for i in range(n):
a.append(s)
s = s[1:] + s[0]
# 对数组a排序，返回字典序最小的字符串
a.sort()
return a[0]
else:
# 当k>1时，直接对原字符串的字符进行排序
cur = list(s)
cur.sort()
ans = "".join(cur)
return ans
在k=1的情况下，我们的操作仅限于将字符串的首个字符移动到末尾，这种操作实际上生成了字符串的所有可能的旋转版本。每次操作后的结果都是原字符串的一个旋转形式，因此，对于一个长度为n的字符串，它有n种可能的旋转形式。例如，字符串's'的所有旋转包括其自身及其所有可能的旋转。当这些旋转形式被放入数组并进行排序时，数组的第一个元素自然是这些旋转中字典序最小的。这是因为排序本质上是将所有元素按字典序排列，而数组中的第一个元素就是所有可能旋转中字典序最小的。
当k>1时，我们可以从字符串的前k个字符中选择任意一个来移动到字符串的末尾。这实际上允许我们对前k个字符进行任意排列，进而通过多次操作，可以改变整个字符串的顺序。由于我们可以自由排列前k个字符，通过足够的操作，我们可以实现原字符串的任何排列。因此，这意味着我们可以通过选择合适的操作顺序来重新排列整个字符串。所以，直接将原字符串的所有字符按照字典序排序，得到的结果就是我们通过任意次操作可能得到的字典序最小的字符串。不存在其他特定的字符移动方式能得到更小的字典序结果，因为排序已使得每个字符都尽可能地处于其在字典序上可能的最前位置。
在k=1的情况下，可以使用一个更高效的算法来寻找字典序最小的旋转字符串，而不必生成所有旋转形式并进行排序。这种方法通常基于字符串的双倍方法和最小表示法。具体做法是，将字符串s重复一次形成新的字符串s+s，这样做的目的是在不断旋转的过程中捕获所有可能的旋转字符串。然后，通过比较每个可能的旋转的起始位置，找到能够生成字典序最小字符串的起始位置。这个起始位置可以使用高效的字符串比较算法（比如最小表示法）来找到。这种方法的时间复杂度通常优于生成所有旋转形式并排序的方法，因为它直接在连续的内存块上进行操作，并且利用了字符串比较的高效性。