Orderly Queue: When One Move Changes Everything

LeetCode Orderly Queue (problem 899) is one of those rare problems where a single number flips the entire solution strategy. You are given a string s and an integer k. In each move, you pick one of the first k characters and move it to the end of the string. Your goal is to return the lexicographically smallest string you can produce after any number of moves.

The problem

Given a string s and an integer k, you can repeatedly choose one of the first k characters of s and append it to the end. Return the lexicographically smallest string possible after applying any number of these operations.

The brute force approach

The naive way to think about this is to simulate every possible sequence of moves. At each step, you have k choices for which character to send to the back. After enough moves, you compare all reachable strings and return the smallest one.

The problem with brute force is that the search space explodes. Each move branches into k possibilities, and you may need many moves to reach the optimal result. For k = 1, the number of reachable strings is bounded by n (the length of the string), since you are just rotating. But for larger k, the state space grows fast, and brute-force simulation becomes impractical.

Fortunately, you do not need simulation at all. The structure of this problem allows a clean closed-form solution.

The key insight

Everything hinges on whether k equals 1 or is greater than 1.

When k = 1, your only move is to take the first character and send it to the back. That is exactly a left rotation. You can produce at most n distinct strings (one for each rotation), and the answer is the lexicographically smallest among them.

When k >= 2, something remarkable happens: you can achieve any permutation of the string. The intuition is that having two characters to choose from at the front gives you enough freedom to perform adjacent swaps. And adjacent swaps are all you need to sort, just like bubble sort. Since you can reach any permutation, the smallest possible string is simply the sorted version.

Step-by-step walkthrough

The code

def orderly_queue(s: str, k: int) -> str:
    if k == 1:
        return min(s[i:] + s[:i] for i in range(len(s)))
    return "".join(sorted(s))

The solution is remarkably short. When k is 1, you generate all n rotations by slicing the string at every index and picking the smallest. When k is 2 or more, you sort the characters and join them back together. That is the entire function.

The min() call over the generator expression handles the k = 1 case efficiently. Python's string comparison is lexicographic by default, so min returns the rotation that comes first alphabetically. For the k >= 2 case, sorted() produces the characters in ascending order, and "".join() reassembles them into a string.

Complexity analysis

For k = 1, you generate n rotations and each rotation takes O(n) to construct and compare, giving O(n^2) overall. For k >= 2, sorting the string takes O(n log n). In both cases, you need O(n) space for the result string. The overall complexity is O(n^2) in the worst case, dominated by the k = 1 path.

The building blocks

String rotation enumeration

When k = 1, you need to enumerate all rotations of a string. The pattern s[i:] + s[:i] generates the rotation starting at index i. This is the same technique used in Rotate String, where you check if one string is a rotation of another by looking for it inside the doubled string. Here, instead of checking membership, you compare all rotations to find the minimum.

Sorting as a permutation shortcut

When k >= 2, the answer is the sorted string. This connects to a fundamental idea in combinatorics: if you can perform any adjacent swap, you can reach any permutation, and in particular you can reach the sorted order. This same principle underlies problems like Sort Colors, where adjacent swaps partition elements, and Next Permutation, where you navigate the permutation space one step at a time.

Edge cases

• k = 1 with an already-sorted string. The original string is its own smallest rotation (or one of them). The algorithm handles this correctly because the original is included in the set of rotations.
• k = 1 with all identical characters. Every rotation is the same string. The min call returns any of them, which is correct.
• k greater than the string length. When k >= n, you can pick any character to move. This is a special case of k >= 2, so you just sort.
• Single-character string. With n = 1, there is only one possible string regardless of k. Both branches return it correctly.
• k = 2 with an already-sorted string. Sorting a sorted string returns itself. No wasted work.

From understanding to recall

This problem is deceptive. The code is short, but the insight behind it requires understanding why k >= 2 unlocks full permutation power. That mathematical leap is the part that fades from memory if you do not practice it.

When you review this problem, focus on the "why" rather than the code itself. Ask yourself: why does having two front slots let you sort? Think through the adjacent swap argument. Picture two characters at the front of the queue and how choosing which one to send back lets you reorder them relative to each other.

Then practice writing the two-branch solution from memory. The k = 1 path (enumerate rotations, pick the minimum) and the k >= 2 path (sort) should feel like a single mental unit. Once you can reproduce the reasoning and the code without looking, you own this problem.

Related posts

• Rotate String - The rotation enumeration technique used in the k = 1 case
• Next Permutation - Navigating permutation space, the foundation for understanding why k >= 2 unlocks all permutations
• Custom Sort String - Another problem where understanding the sorting structure leads to a clean solution