题目描述

给出了一个由小写字母组成的字符串 S。然后，我们可以进行任意次数的 移动 。

在每次移动中，我们选择前 K 个字母中的一个（从左侧开始），将其从原位置移除，并放置在字符串的末尾。

返回我们在任意次数的移动之后可以拥有的按字典顺序排列的最小字符串。

样例

输入：S = "cba", K = 1
输出："acb"
解释：
在第一步中，我们将第一个字符（“c”）移动到最后，获得字符串 “bac”。
在第二步中，我们将第一个字符（“b”）移动到最后，获得最终结果 “acb”。

输入：S = "baaca", K = 3
输出："aaabc"
解释：
在第一步中，我们将第一个字符（“b”）移动到最后，获得字符串 “aacab”。
在第二步中，我们将第三个字符（“c”）移动到最后，获得最终结果 “aaabc”。

注意

• 1 <= K <= S.length <= 1000
• S 只由小写字母组成。

算法

(找规律) $O(n^2)$

1. 当 K == 1 时，显然我们只能每次将开头的一次字符移动到末尾，这样我们的备选答案一共就只有 $n$ 种，枚举每一种找到字典序最小的即可。
2. 当 K > 1 时，可以证明其可以转换为任意的串。假设我们希望交换 S[i] 和 S[i + 1]，只需要将 [0, i- 1] 的字符移动到末尾，然后将 S[i + 1] 移动到末尾，再将 S[i] 移动到末尾，再将 [i + 2, n - 1] 移动到末尾。有了交换相邻字符的操作，可以利用冒泡排序排出字典序最小的串。

时间复杂度

• 当 K == 1 时，需要构造 $n$ 种备选答案，每次构造和比较答案需要 $O(n)$ 的时间，故需要 $O(n^2)$ 的时间；
• 当 K > 1 时，直接利用 sort 排序即可，需要 $O(n \log n)$ 的时间。
• 故总时间复杂度为 $O(n^2)$。

空间复杂度

• 当 K == 1 时需要临时的字符串空间，故空间复杂度为 $O(n)$。

C++ 代码

class Solution {
public:
    string orderlyQueue(string S, int K) {
        if (K > 1) {
            sort(S.begin(), S.end());
            return S;
        }
        int n = S.length();
        string ans(S);
        S += S;
        for (int i = 1; i < n; i++)
            ans = min(ans, S.substr(i, n));
        return ans;
    }
};