LeetCode 899: Orderly Queue

Problem Restatement

We are given a string s and an integer k.

In one operation:

1. Choose one of the first k characters of s.
2. Remove it from its current position.
3. Append it to the end of the string.

Return the lexicographically smallest string we can get after any number of operations.

Input and Output

Function shape:

def orderlyQueue(self, s: str, k: int) -> str:
    ...

Examples

Example 1:

Input: s = "cba", k = 1
Output: "acb"

When k = 1, we can only move the first character to the end.

Starting from "cba":

cba -> bac -> acb -> cba

The possible strings are rotations of the original string.

The smallest rotation is:

acb

Example 2:

Input: s = "baaca", k = 3
Output: "aaabc"

When k > 1, we can rearrange the characters freely.

So the smallest possible string is the sorted string:

aaabc

First Thought: Simulate All Operations

A direct approach is to explore every string reachable by the operation.

For each string, try moving each of the first k characters to the end.

This creates a graph of string states.

Then we could search all reachable strings and keep the lexicographically smallest one.

This is too expensive. The number of string permutations can be very large.

We need to use the structure of the operation.

Key Insight

There are two different cases.

Case 1: k == 1

If k = 1, the only allowed move is:

move the first character to the end

This is exactly a rotation.

So the reachable strings are only:

s[0:] + s[:0]
s[1:] + s[:1]
s[2:] + s[:2]
...

We just need the smallest rotation.

Case 2: k > 1

If k >= 2, the operation is powerful enough to produce any permutation of the characters.

Since any permutation is reachable, the lexicographically smallest reachable string is simply the sorted characters of s.

So the answer is:

"".join(sorted(s))

Why k > 1 Allows Sorting

When k >= 2, we can choose either the first or second character and move it to the end.

This gives enough control to change the relative order of adjacent characters over repeated operations.

Once adjacent reordering is possible, any permutation can be formed because any permutation can be produced by a sequence of adjacent swaps.

Therefore, for k > 1, all character permutations are reachable.

The smallest permutation is the sorted string.

Algorithm

If k == 1:

1. Generate all rotations of s.
2. Return the lexicographically smallest rotation.

If k > 1:

1. Sort the characters of s.
2. Return the sorted string.

Walkthrough

Use:

s = "cba"
k = 1

All rotations:

Smallest:

acb

Use:

s = "baaca"
k = 3

Since k > 1, sort all characters:

a, a, a, b, c

Answer:

aaabc

Correctness

If k == 1, every operation moves only the first character to the end. Repeating this operation rotates the string. No other reordering is possible because the relative order of all characters remains cyclically fixed. The algorithm checks every rotation and returns the smallest one, so it is correct for this case.

If k > 1, the operation can generate arbitrary permutations of the characters. Therefore, the set of reachable strings contains every ordering of the same multiset of characters. Among all permutations of a multiset, the lexicographically smallest one is the sorted order. The algorithm returns that sorted order, so it is correct for this case.

Since these two cases cover all possible values of k, the algorithm is correct.

Complexity

Let:

n = len(s)

For k == 1, we build n rotations, each of length n.

Implementation

class Solution:
    def orderlyQueue(self, s: str, k: int) -> str:
        if k == 1:
            best = s

            for i in range(1, len(s)):
                rotated = s[i:] + s[:i]
                if rotated < best:
                    best = rotated

            return best

        return "".join(sorted(s))

Code Explanation

When k == 1, we start with the original string as the best answer:

best = s

Then we try every rotation:

for i in range(1, len(s)):
    rotated = s[i:] + s[:i]

If a rotation is smaller, update the answer:

if rotated < best:
    best = rotated

When k > 1, return the sorted string:

return "".join(sorted(s))

Testing

def run_tests():
    s = Solution()

    assert s.orderlyQueue("cba", 1) == "acb"
    assert s.orderlyQueue("baaca", 3) == "aaabc"
    assert s.orderlyQueue("abc", 1) == "abc"
    assert s.orderlyQueue("bca", 1) == "abc"
    assert s.orderlyQueue("dcba", 2) == "abcd"
    assert s.orderlyQueue("aaaa", 1) == "aaaa"

    print("all tests passed")

run_tests()

Test meaning: