#899

Hard

LeetCode Problem Workspace

Orderly Queue

Given a string and integer k, rearrange characters to achieve the lexicographically smallest string using limited rotations.

math string sorting

Problem Statement

You are given a string s and an integer k. You may choose one of the first k letters of s and move it to the end of the string any number of times. The goal is to transform s into the lexicographically smallest string possible through repeated applications of this operation.

Return the lexicographically smallest string obtainable after applying the allowed moves. For example, if s = "cba" and k = 1, repeated rotations produce "acb". If s = "baaca" and k = 3, strategic moves yield "aaabc". All input strings consist of lowercase English letters, and 1 <= k <= s.length.

Examples

Example 1

Input: s = "cba", k = 1

Output: "acb"

In the first move, we move the 1st character 'c' to the end, obtaining the string "bac". In the second move, we move the 1st character 'b' to the end, obtaining the final result "acb".

Example 2

Input: s = "baaca", k = 3

Output: "aaabc"

In the first move, we move the 1st character 'b' to the end, obtaining the string "aacab". In the second move, we move the 3rd character 'c' to the end, obtaining the final result "aaabc".

Constraints

1 <= k <= s.length <= 1000
s consist of lowercase English letters.

Solution Approach

Handle k equals 1 with rotations

When k is 1, only rotations are allowed, so generate all cyclic permutations of s by repeatedly moving the first character to the end. Compare each rotation lexicographically and select the smallest one as the answer.

Handle k greater than 1 with sorting

If k > 1, the problem simplifies because any sequence of moves can simulate a bubble sort, allowing characters to rearrange freely. Sort the characters of s in ascending order to obtain the lexicographically smallest string efficiently.

Optimize for combined patterns

For strings where k = 1 but length is small, compare all rotations directly. For larger strings or k > 1, apply a single sorted transformation. This approach balances string manipulation with mathematical analysis of rotations and possible moves.

Complexity Analysis

Metric	Value
Time	Depends on the final approach
Space	Depends on the final approach

For k = 1, generating all n rotations takes O(n^2) time and O(n) space per rotation comparison. For k > 1, sorting the string takes O(n log n) time and O(n) space. Overall, complexity depends on k and string length n.

What Interviewers Usually Probe

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

Common Pitfalls or Variants

Common pitfalls

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

Follow-up variants

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

FAQ

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.

terminal

Solution

Solution 1: Case-by-case Judgment

If $k = 1$, we can only move the first character of the string to the end of the string each time, resulting in $|s|$ different states. We return the string with the smallest lexicographic order.

1

2

3

4

5

6

7

8

9

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))

Continue Practicing

#539 minimum time difference #902 numbers at most n given digit set #893 groups of special equivalent strings