【LeetCode】899. 有序队列

题目

899. 有序队列

给定一个字符串 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 <= 1000
• s 只由小写字母组成。

思路

• 若$k=1$，只有一种情况，遍历所有情况，取最小值
• 若$k>1$，每一次把最小值和最大值分别移到第一格和第二格，然后将最大值移到最后一格，如此反复，字符串必将有序，所以直接输出排序后的字符串

代码

class Solution:
    def orderlyQueue(self, s: str, k: int) -> str:
        if k==1:
            ret = s
            for _ in range(len(s)-1):
                s = s[1:]+s[0]
                ret = min(s,ret)
            return ret
        return ''.join(sorted(s))

复杂度

• 时间复杂度：$O(n^2)$
• 空间复杂度：$O(n)$