---

0899. 有序队列

• 标签：数学、字符串、排序
• 难度：困难

题目链接

• 0899. 有序队列 - 力扣

题目大意

描述：

给定一个字符串 $s$ 和一个整数 $k$。你可以从 $s$ 的前 $k$ 个字母中选择一个，并把它加到字符串的末尾。

要求：

返回在应用上述步骤的任意数量的移动后，字典序最小的字符串。

说明：

• $1 \le k \le S.length \le 10^{3}$。
• $s$ 只由小写字母组成。

示例：

• 示例 1：

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

• 示例 2：

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

解题思路

思路 1:数学 + 排序

这道题的关键在于分析 $k$ 的不同取值:

1. 当 $k = 1$ 时:只能将第一个字符移到末尾,相当于字符串的循环移位。我们需要枚举所有可能的循环移位,找到字典序最小的。

2. 当 $k \ge 2$ 时:可以实现任意两个字符的交换,因此可以得到任意排列。此时答案就是将字符串排序后的结果。

证明 $k \ge 2$ 时可以交换任意两个字符:

• 假设要交换位置 $i$ 和 $j$ 的字符($i < j$)
• 可以通过一系列操作,将这两个字符移到相邻位置,然后交换它们

思路 1:代码

class Solution:
    def orderlyQueue(self, s: str, k: int) -> str:
        if k == 1:
            # k = 1 时,枚举所有循环移位
            result = s
            for i in range(len(s)):
                # 将前 i 个字符移到末尾
                rotated = s[i:] + s[:i]
                if rotated < result:
                    result = rotated
            return result
        else:
            # k >= 2 时,可以得到任意排列,返回排序后的字符串
            return ''.join(sorted(s))

思路 1:复杂度分析

• 时间复杂度:$O(n^2)$,其中 $n$ 是字符串的长度。当 $k = 1$ 时,需要枚举 $n$ 种循环移位,每次比较需要 $O(n)$;当 $k \ge 2$ 时,排序需要 $O(n \log n)$。
• 空间复杂度:$O(n)$,需要存储结果字符串。