899. 有序队列

Difficulty
Medium
Tags
排序
URL
https://leetcode.cn/problems/orderly-queue/
Star
给定一个字符串 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 只由小写字母组成。
通过次数14,709提交次数23,334

排序

思路
当 k ≥ 2 的时候，像冒泡排序，每次都从前k个中找最小的放到最后。
当k == 1的时候，其实不断的往后移动一个字符，就是一个圈了，本质上是在找一个起点。
题解
class Solution:
    def orderlyQueue(self, s: str, k: int) -> str:
        if k == 1:
            res = s
            for i in range(0, len(s)):
                res = min(res, s[i:]+s[0:i])
        else:
            res = "".join(sorted(list(s)))

        return res