What is the main pattern in the Orderly Queue problem?

The problem combines Math with String manipulation, analyzing rotations and sorting to reach the minimal lexicographic string.

How do I solve Orderly Queue when k equals 1?

Generate all cyclic rotations of the string by moving the first character repeatedly, then pick the smallest rotation lexicographically.

How do I solve Orderly Queue when k is greater than 1?

Sort the string in ascending order since repeated moves allow any character ordering, guaranteeing the smallest lexicographic result.

What are common mistakes in this problem?

Ignoring the k = 1 rotation restriction, performing unnecessary operations for k > 1, or not comparing rotations correctly.

Can this approach scale to large strings?

Yes, for k > 1 sorting is efficient with O(n log n), but for k = 1 each rotation check is O(n^2), so optimization is needed for large n.

#899

Hard

auto_awesome数学·string

LeetCode 题解工作台

有序队列

给定一个字符串 s 和一个整数 k 。你可以从 s 的前 k 个字母中选择一个，并把它加到字符串的末尾。返回在应用上述步骤的任意数量的移动后，字典序最小的字符串。示例 1：输入： s = "cba", k = 1 输出： "acb" 解释：在第一步中，我们将第一个字符（“c”）移动到最后…

数学字符串排序

题目描述

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

lightbulb

解题思路

方法一：分情况判断

若 $k = 1$ ，我们每次只能将字符串首字符移动到字符串末尾，总共有 $|s|$ 种不同的状态，我们返回其中字典序最小的字符串即可。

若 $k \gt 1$ ，对于形如 $abc[xy]def$ 的字符串，可以依次将 $a$ , $b$ , $c$ 移动到最后，得到 $[xy]defabc$ ，然后将 $y$ , $x$ 移动到最后，得到 $defabc[yx]$ ，最后将 $d$ , $e$ , $f$ 移动到最后，得到 $abc[yx]def$ ，这样就实现了对 $y$ , $x$ 的交换。

因此，只要 $k \gt 1$ ，我们就能够交换字符串中的任何两个相邻字符，最终得到一个升序排列的字符串。

时间复杂度 $O(n^2)$ ，空间复杂度 $O(n)$ 。其中 $n$ 是字符串的长度。

1

2

3

4

5

6

7

8

9

10

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

speed

复杂度分析

指标	值
时间	Depends on the final approach
空间	Depends on the final approach

psychology

面试官常问的追问

外企场景

question_mark
Check if the candidate recognizes the special case when k = 1 versus k > 1.
question_mark
Notice if the candidate efficiently compares rotations without redundant string copies.
question_mark
Evaluate whether the candidate leverages sorting when k > 1 to reduce operations.

warning

常见陷阱

外企场景

error
Assuming k > 1 can be treated like k = 1 and only rotating characters.
error
Overlooking that k = 1 requires considering all cyclic permutations.
error
Performing unnecessary operations for k > 1 instead of direct sorting.

swap_horiz

进阶变体

外企场景

arrow_right_alt
Allowing multiple character moves at once instead of only one within the first k.
arrow_right_alt
Finding the lexicographically largest string instead of the smallest.
arrow_right_alt
Restricting moves to only the first character regardless of k value.

help

常见问题

外企场景

继续练习

#539 最小时间差 #902 最大为 N 的数字组合 #893 特殊等价字符串组