# 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

| Item | Meaning |
|---|---|
| Input | String `s` |
| Input | Integer `k` |
| Output | Lexicographically smallest reachable string |
| Operation | Move one of the first `k` characters to the end |
| Repetitions | Any number of operations is allowed |

Function shape:

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

## Examples

Example 1:

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

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

Starting from `"cba"`:

```text
cba -> bac -> acb -> cba
```

The possible strings are rotations of the original string.

The smallest rotation is:

```text
acb
```

Example 2:

```text
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:

```text
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:

```text
move the first character to the end
```

This is exactly a rotation.

So the reachable strings are only:

```text
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:

```python
"".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:

```text
s = "cba"
k = 1
```

All rotations:

| Rotation | String |
|---:|---|
| 0 | `cba` |
| 1 | `bac` |
| 2 | `acb` |

Smallest:

```text
acb
```

Use:

```text
s = "baaca"
k = 3
```

Since `k > 1`, sort all characters:

```text
a, a, a, b, c
```

Answer:

```text
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:

```text
n = len(s)
```

| Case | Time | Space |
|---|---:|---:|
| `k == 1` | `O(n^2)` | `O(n)` |
| `k > 1` | `O(n log n)` | `O(n)` |

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

## Implementation

```python
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:

```python
best = s
```

Then we try every rotation:

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

If a rotation is smaller, update the answer:

```python
if rotated < best:
    best = rotated
```

When `k > 1`, return the sorted string:

```python
return "".join(sorted(s))
```

## Testing

```python
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:

| Test | Why |
|---|---|
| `"cba", k = 1` | Only rotations are possible |
| `"baaca", k = 3` | Sorting case |
| `"abc", k = 1` | Already smallest rotation |
| `"bca", k = 1` | Rotation can produce sorted order |
| `"dcba", k = 2` | `k > 1` allows full sorting |
| `"aaaa", k = 1` | All rotations are equal |