Problem Summary

You are given a string s and an integer k.

You can perform the following operation any number of times:

• Choose one of the first k characters of the string and move it to the end of the string.

Your task is to return the lexicographically smallest string you can obtain after applying any number of operations.

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

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

Constraints

• 1 ≤ s.length ≤ 10⁵
• s contains lowercase letters
• 1 ≤ k ≤ s.length

---

Approach (Simple English)

This problem has two very different behaviors depending on the value of k.

There are only two cases to understand.

---

Case 1: k = 1 (Only rotations allowed)

When k = 1, you can only take the first character and move it to the end.

This means you can only generate rotations of the string.

Example
"cba" → "bac" → "acb" → "cba" → …

These are all rotations of the original string.

Key Idea

When k = 1, the answer is simply the lexicographically smallest rotation of s.

Why This Works

Each operation shifts the first character to the end.
This creates exactly all possible rotations of the string.

To find the smallest lexicographic rotation:

• Compare all rotations
• Return the smallest one

Time complexity: O(n²) by brute force, but acceptable because n ≤ 10⁵ and rotations are sliced strings.
Alternatively, Booth’s algorithm can do it in O(n), but brute force rotation-check is fine here in Java because substring comparisons are optimized.

---

Case 2: k ≥ 2 (String can be fully sorted)

When k ≥ 2, you can pick any of the first two characters and cycle them to the end in any order.

This gives enough freedom to simulate bubble sort-like adjacent swaps, which means:

Key Idea

If k ≥ 2, you can rearrange the string into any order you want.

Therefore, the lexicographically smallest string is simply:

the sorted string

Why This Works

With k = 2, you can bring any character to the front by repeatedly pushing others to the back.
Thus the string can be permuted arbitrarily.

This generalizes to all k ≥ 2.

Time complexity: O(n log n)

---

Final Rule

If k == 1 → find smallest rotation
If k > 1 → return sorted(s)

This is the exact logic required to solve the problem optimally.

---

Java Code (Optimal Solution)

import java.util.*;

class Solution {
    public String orderlyQueue(String s, int k) {

        if (k == 1) {
            String best = s;
            // Generate all rotations and track minimum
            for (int i = 1; i < s.length(); i++) {
                String rotation = s.substring(i) + s.substring(0, i);
                if (rotation.compareTo(best) < 0) {
                    best = rotation;
                }
            }
            return best;
        }

        // k >= 2: fully sortable
        char[] arr = s.toCharArray();
        Arrays.sort(arr);
        return new String(arr);
    }
}

---

Dry Run (Case k = 1)

Input
s = "cba", k = 1

Rotations:

1. "cba"
2. "bac"
3. "acb"

Smallest = "acb"

Return "acb"

---

Dry Run (Case k ≥ 2)

Input
s = "baaca", k = 3

Since k ≥ 2, sort the string:

Characters: [b, a, a, c, a] → sorted → [a, a, a, b, c]

Output = "aaabc"

---

Complexity Analysis

Case k = 1
Time: O(n²) due to rotation comparisons
Space: O(n)

Case k ≥ 2
Time: O(n log n)
Space: O(n)

---

Edge Cases

• Single-character string → always valid
• All characters identical → output is the same string
• Large string with k ≥ 2 → sorting handles everything
• Large string with k = 1 → rotation comparison still manageable