困难

问题描述

给定一个字符串 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$，每一步只能选取头部的字母放到最后，字符串相当于是一个环，此时只需枚举字符串的所有情况，找出字典序最小的即可。
• 若 $k > 1$，通过不断交换字符，最终字符串可以排列成升序，此过程类似于冒泡排序，因此直接将字符串按字典序排序返回即可。

/**
 * @param {string} s
 * @param {number} k
 * @return {string}
 */
var orderlyQueue = function (s, k) {
  if (k === 1) {
    const n = s.length
    const ss = s + s
    let queue = s
    for (let i = 1; i < n; i++) {
      const tmp = ss.substring(i, i + n)
      if (queue > tmp) queue = tmp
    }
    return queue
  }
  return s.split('').sort().join('')
}

• 时间复杂度：$O(n^2)$ 或 $O(n\log{n})$，当$k > 1$时，快速排序时间复杂度为 $O(n\log{n})$，当$k = 1$时，枚举所有字符串时间复杂度为 $O(n^2)$
• 空间复杂度：$O(n)$ 或 $O(\log{n})$，当$k > 1$时，快速排序空间复杂度为 $O(log{n})$，当$k = 1$时，枚举所有字符串复杂度为 $O(n)$