# Orderly Queue
**Difficulty:** HARD
[External](https://leetcode.com/problems/orderly-queue)
Canonical: https://scaleengineer.com/dsa/problems/orderly-queue
**Patterns:** [Math](https://scaleengineer.com/dsa/patterns/math)
**Algorithms:** [Sorting](https://scaleengineer.com/algorithms/sorting)
**Data structures:** String
---
## Problem
You are given a string `s` and an integer `k`. You can choose one of the first `k` letters of `s` and append it at the end of the string.

Return _the lexicographically smallest string you could have after applying the mentioned step any number of moves_.

**Example 1:**

**Input:** s = "cba", k = 1
**Output:** "acb"
**Explanation:** 
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"
**Explanation:** 
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.

# Approaches
## Case Analysis with O(n^2) Rotation Search
A crucial observation is that the problem's nature changes dramatically based on the value of `k`. This approach handles the two cases, `k=1` and `k>1`, separately. For `k>1`, it correctly identifies that any permutation is possible, so sorting the string gives the answer. For `k=1`, it uses a simple simulation to find the best rotation by generating all `n` possibilities and comparing them, which results in a quadratic time complexity for this case.
**Time:** O(n^2), where n is the length of the string. The `k>1` case takes `O(n log n)` for sorting. The `k=1` case involves a loop that runs `n` times, and inside it, string comparison takes `O(n)`, leading to an `O(n^2)` complexity. The overall complexity is the worse of the two, which is `O(n^2)`. · **Space:** O(n), where n is the length of the string. This space is used for the character array in the `k>1` case or the `StringBuilder` in the `k=1` case.
**Pros:** Much more efficient than a full brute-force search.; The logic is straightforward and relatively easy to implement.; Correctly solves the problem and passes within typical time limits for the given constraints.
**Cons:** The time complexity is dominated by the `k=1` case, which is `O(n^2)`, making it slower than the optimal approach for large `n`.
### Explanation
The algorithm is split into two main scenarios:

1.  **If `k > 1`**: We can achieve any permutation of the string `s`. The proof sketch is that with `k>1`, we can perform an adjacent swap. Since any permutation can be reached by a series of adjacent swaps (like in bubble sort), we can form any arrangement of characters. To get the lexicographically smallest string, we just need to sort the characters of `s`. This can be done by converting the string to a character array, sorting it, and converting it back to a string.

2.  **If `k = 1`**: We can only perform cyclic shifts. To find the lexicographically smallest one, this approach iterates through all `n` possible rotations. It maintains a variable `smallest` that stores the best rotation found so far. In a loop, it generates the next rotation and updates `smallest` if the new rotation is lexicographically smaller.

```java
import java.util.Arrays;

class Solution {
    public String orderlyQueue(String s, int k) {
        if (k > 1) {
            char[] chars = s.toCharArray();
            Arrays.sort(chars);
            return new String(chars);
        } else { // k == 1
            String smallest = s;
            StringBuilder sb = new StringBuilder(s);
            // Iterate through all n-1 possible rotations
            for (int i = 1; i < s.length(); i++) {
                // Rotate the string by one position
                char first = sb.charAt(0);
                sb.deleteCharAt(0);
                sb.append(first);
                String rotated = sb.toString();
                // Compare with the smallest found so far
                if (rotated.compareTo(smallest) < 0) {
                    smallest = rotated;
                }
            }
            return smallest;
        }
    }
}
```
### Algorithm
- The core idea is to analyze the problem based on the value of `k`.
- **Case 1: `k > 1`**
  - When `k` is greater than 1, we have enough flexibility to swap any two adjacent characters in the string. This is because we can bring any two adjacent characters to the first two positions (by repeatedly moving the first character to the end), and since `k > 1`, we can manipulate them. For instance, to swap `s_1` and `s_2`, we can move `s_1` to the end, then cycle all other characters through until `s_2` is at the front followed by `s_1`. 
  - The ability to swap any adjacent pair implies we can achieve any permutation of the string (this is the principle behind bubble sort).
  - Therefore, the lexicographically smallest string we can form is simply the sorted version of the original string `s`.
- **Case 2: `k = 1`**
  - When `k` is 1, the only allowed move is to take the first character and move it to the end. This is a cyclic shift or rotation of the string.
  - The problem reduces to finding the lexicographically smallest string among all possible rotations of `s`.
  - This approach implements a straightforward, albeit inefficient, method for this case: generate all `n` rotations and compare them to find the smallest one.

## Optimal Case Analysis with Sorting
This approach refines the previous one by optimizing the `k=1` case. While the `O(n^2)` solution for finding the smallest rotation is acceptable for the given constraints, a more advanced linear-time `O(n)` algorithm exists for this classic string problem. By employing this optimal algorithm for the `k=1` case, the overall time complexity of the solution is improved, being dominated by the `O(n log n)` sorting step required for the `k>1` case.
**Time:** O(n log n). The `k>1` case is `O(n log n)`. The `k=1` case is solved in `O(n)`. The overall complexity is `max(O(n log n), O(n))`, which simplifies to `O(n log n)`. · **Space:** O(n). Space is required for the character array (`k>1`) or the duplicated string `s+s` (`k=1`).
**Pros:** Provides the most efficient solution with the best possible time complexity.; Demonstrates knowledge of both the problem's core insight and advanced string algorithms.
**Cons:** The linear-time algorithm for finding the smallest rotation is more complex to understand and implement correctly compared to the simple `O(n^2)` loop.
### Explanation
This solution also splits the problem based on `k`.

- **If `k > 1`**: The logic is unchanged. Sorting the string is the optimal solution, taking `O(n log n)` time.

- **If `k = 1`**: We use a linear-time, two-pointer algorithm to find the lexicographically smallest rotation. This avoids the quadratic complexity of naive comparison. The implementation can be made cleaner by working on a duplicated string `s+s`, which simplifies index handling.

By optimizing the `k=1` case to `O(n)`, the overall time complexity becomes `max(O(n log n), O(n))`, which is `O(n log n)`. This is asymptotically the best possible solution.

```java
import java.util.Arrays;

class Solution {
    public String orderlyQueue(String s, int k) {
        if (k > 1) {
            char[] chars = s.toCharArray();
            Arrays.sort(chars);
            return new String(chars);
        } else { // k == 1, solved in O(n)
            return findSmallestRotation(s);
        }
    }

    // Finds the lexicographically smallest rotation of a string in O(n) time.
    private String findSmallestRotation(String s) {
        int n = s.length();
        String s2 = s + s; // Use a doubled string to simplify comparisons
        int i = 0; // Index of the first candidate rotation
        int j = 1; // Index of the second candidate rotation
        
        while (i < n && j < n) {
            int k = 0; // Number of matching characters
            while (k < n && s2.charAt(i + k) == s2.charAt(j + k)) {
                k++;
            }
            if (k == n) { // The entire string matches, all rotations are the same
                break;
            }
            // If character at s[i+k] is greater, rotation i is not the smallest.
            // The new candidate for i can start after the mismatched block.
            if (s2.charAt(i + k) > s2.charAt(j + k)) {
                i = i + k + 1;
            } else { // s2.charAt(i + k) < s2.charAt(j + k)
                j = j + k + 1;
            }
            // Ensure i and j are not the same
            if (i == j) {
                j++;
            }
        }
        // The starting index of the smallest rotation is the minimum of the final candidates.
        int minIndex = Math.min(i, j);
        return s2.substring(minIndex, minIndex + n);
    }
}
```
### Algorithm
- The logic for the `k > 1` case is identical to the previous approach: sort the string. This is the optimal strategy for this case and takes `O(n log n)` time.
- For the `k = 1` case, instead of an `O(n^2)` search, this approach uses an efficient `O(n)` algorithm to find the lexicographically smallest rotation.
- One such linear-time algorithm works by maintaining two pointers, `i` and `j`, representing the starting indices of two candidate rotations. 
- We compare the rotations starting at `i` and `j` character by character. Let `k` be the number of characters they have in common from the start.
- If `s[i+k] > s[j+k]`, the rotation at `i` is worse, so we can discard it and advance `i` past the compared block (`i = i + k + 1`).
- If `s[i+k] < s[j+k]`, the rotation at `j` is worse, so we advance `j` (`j = j + k + 1`).
- This process continues until one pointer has traversed the entire string length, and the minimum of the final `i` and `j` gives the starting index of the smallest rotation.

# Solutions
### Java

```java
class Solution { public String orderlyQueue ( String s , int k ) { if ( k == 1 ) { String ans = s ; StringBuilder sb = new StringBuilder ( s ); for ( int i = 0 ; i < s . length () - 1 ; ++ i ) { sb . append ( sb . charAt ( 0 )). deleteCharAt ( 0 ); if ( sb . toString (). compareTo ( ans ) < 0 ) { ans = sb . toString (); } } return ans ; } char [] cs = s . toCharArray (); Arrays . sort ( cs ); return String . valueOf ( cs ); } }
```

### CPP

```cpp
class Solution { public: string orderlyQueue ( string s , int k ) { if ( k == 1 ) { string ans = s ; for ( int i = 0 ; i < s . size () - 1 ; ++ i ) { s = s . substr ( 1 ) + s [ 0 ]; if ( s < ans ) ans = s ; } return ans ; } sort ( s . begin (), s . end ()); return s ; } };
```

### Python

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