Hard

题目描述

给定一个字符串 s 和一个整数 k。你可以选择字符串前 k 个字母中的任意一个，并将其移动到字符串的末尾。

返回在进行任意次数的移动操作后，能够得到的字典序最小的字符串。

示例 1：

输入：s = "cba", k = 1
输出："acb"
解释：
第一步，移动第1个字符'c'到末尾，得到字符串"bac"。
第二步，移动第1个字符'b'到末尾，得到最终结果"acb"。

示例 2：

输入：s = "baaca", k = 3
输出："aaabc"
解释：
第一步，移动第1个字符'b'到末尾，得到字符串"aacab"。
第二步，移动第3个字符'c'到末尾，得到最终结果"aaabc"。

约束条件：

  • 1 <= k <= s.length <= 1000
  • s 由小写英文字母组成

解题思路

这是一道需要深入理解操作规律的数学题。关键在于分析不同 k 值下能够达到的状态空间。

核心观察：

  1. 当 k = 1 时： 只能选择第一个字符移动到末尾，这相当于字符串的循环左移操作。我们只能得到原字符串的所有旋转变体，需要在这些变体中找到字典序最小的。

  2. 当 k ≥ 2 时： 情况会发生质变。通过巧妙的操作组合，我们可以实现任意两个相邻字符的交换：

    • 先将第二个字符移到末尾
    • 再将第一个字符移到末尾
    • 通过适当的后续操作，可以实现相邻字符交换

    由于任意两个相邻字符都可以交换，根据冒泡排序的原理，我们可以将字符串排列成任意顺序。因此最优解就是将所有字符按字典序排序。

算法实现：

  • k = 1：生成所有旋转字符串，返回字典序最小的
  • k ≥ 2：直接对字符排序

这个解法的精妙之处在于将复杂的操作序列问题转化为对操作能力边界的数学分析。

代码实现

class Solution {
public:
    string orderlyQueue(string s, int k) {
        if (k == 1) {
            string result = s;
            for (int i = 1; i < s.length(); i++) {
                string rotated = s.substr(i) + s.substr(0, i);
                if (rotated < result) {
                    result = rotated;
                }
            }
            return result;
        } else {
            sort(s.begin(), s.end());
            return s;
        }
    }
};

class Solution:
    def orderlyQueue(self, s: str, k: int) -> str:
        if k == 1:
            result = s
            for i in range(1, len(s)):
                rotated = s[i:] + s[:i]
                if rotated < result:
                    result = rotated
            return result
        else:
            return ''.join(sorted(s))

public class Solution {
    public string OrderlyQueue(string s, int k) {
        if (k == 1) {
            string result = s;
            for (int i = 1; i < s.Length; i++) {
                string rotated = s.Substring(i) + s.Substring(0, i);
                if (string.Compare(rotated, result) < 0) {
                    result = rotated;
                }
            }
            return result;
        } else {
            char[] chars = s.ToCharArray();
            Array.Sort(chars);
            return new string(chars);
        }
    }
}

var orderlyQueue = function(s, k) {
    if (k === 1) {
        let result = s;
        for (let i = 1; i < s.length; i++) {
            let rotated = s.slice(i) + s.slice(0, i);
            if (rotated < result) {
                result = rotated;
            }
        }
        return result;
    } else {
        return s.split('').sort().join('');
    }
};
在 LeetCode 上运行： 力扣中文版 LeetCode 国际版

复杂度分析

操作时间复杂度空间复杂度
k = 1O(n²)O(n)
k ≥ 2O(n log n)O(n)

说明：

  • 当 k = 1 时，需要生成 n 个旋转字符串并比较，每次比较需要 O(n) 时间
  • 当 k ≥ 2 时，只需要对字符进行排序
  • 空间复杂度主要用于存储结果字符串