难度困难157收藏分享切换为英文接收动态反馈
给定一个字符串 s 和一个整数 k 。你可以从 s 的前 k 个字母中选择一个，并把它加到字符串的末尾。
返回 在应用上述步骤的任意数量的移动后，字典上最小的字符串 。
示例 1：
1
2
3
4
5
| 输入：s = "cba", k = 1
输出："acb"
解释：
在第一步中，我们将第一个字符（“c”）移动到最后，获得字符串 “bac”。
在第二步中，我们将第一个字符（“b”）移动到最后，获得最终结果 “acb”。
|
示例 2：
1
2
3
4
5
| 输入：s = "baaca", k = 3
输出："aaabc"
解释：
在第一步中，我们将第一个字符（“b”）移动到最后，获得字符串 “aacab”。
在第二步中，我们将第三个字符（“c”）移动到最后，获得最终结果 “aaabc”。
|
提示：
1 <= k <= S.length <= 1000s 只由小写字母组成。
题解
可以分为两种情况：
- k=1的时候，可能的变化是循环的将第一个字符放在末尾，只可能出现n种字符串，可以直接遍历这些字符串，然后存储最先字典序的字符串即可
- k>1的时候，可以生成任意顺序的字符串，所以可以直接对字符串的字符进行排序，得到字典序最小的字符串返回
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
| public class Solution {
public String orderlyQueue(String s, int k) {
if (k == 1) {
String ans = s;
for (int i = 1; i < s.length(); i++) {
String t = s.substring(i) + s.substring(0, i);
if (t.compareTo(ans) < 0) ans = t;
}
return ans;
}
char[] c = s.toCharArray();
Arrays.sort(c);
return new String(c);
}
}
|
- 时间复杂度：$O(n^2)$
- 空间复杂度：$O(n)$
