Orderly Queue — Solution in Python, Java & C++
Orderly Queue solution explained: step-by-step approach, complexity and code in Python, Java, C++ and JavaScript. A hard problem, asked at Amazon and Google.
Orderly Queue is a hard coding problem on strings, math and sorting, asked in Amazon and Google interviews.
- Difficulty: Hard
- Topics: Strings, Math, Sorting
- Asked at: Amazon, Google
- Time limit: 2 s
- Memory limit: 256 MB
- Languages: JavaScript, TypeScript, Python, Java, C++, C, C#, Go, Kotlin, Swift, Rust, PHP and Ruby
Problem statement
You are given a string s and an integer k. In one move you choose one of the first k letters of s, remove it, and append it to the end of the string.
You may make any number of moves. Return the lexicographically smallest string you can end up with.
Example 1
Input: s = "kairo", k = 1
Output: airok
Explanation: With `k = 1` only rotations are reachable; the smallest is `airok`.
Example 2
Input: s = "baaca", k = 3
Output: aaabc
Explanation: With `k >= 2` the letters can be put in any order.
Example 3
Input: s = "cba", k = 1
Output: acb
Constraints
1 <= k <= s.length <= 1000s consists of lowercase English letters
Hints for Orderly Queue
Hint 1
With
k = 1each move rotates the string by one position, so the reachable strings are exactly the rotations.Hint 2
With
k = 2you can hold one letter back while the rest rotate past it — that lets you swap two adjacent letters.Hint 3
Adjacent swaps can sort anything, so for
k >= 2the answer is simply the sorted string.
How to solve Orderly Queue
Two cases. With k = 1 the moves are rotations, so try all of them. With k >= 2 any two adjacent letters can be swapped (while the rest rotate around), so every permutation is reachable and the sorted string wins.
Approach
- If
k == 1: compare allnrotationss[i:] + s[:i]and return the smallest. - Otherwise return the letters of
sin sorted order.
Why it works
For k >= 2, view the string as a cycle with a pointer. Moving the first letter to the back advances the pointer; moving the second letter to the back instead swaps the order of the first two letters in the cycle. Rotations plus adjacent swaps generate every permutation — the same reason bubble sort works — so the sorted string is reachable, and nothing is smaller.
Complexity
- Time —
O(n^2) for k = 1, O(n log n) otherwise - Space —
O(n)
Pitfalls
- Simulating moves greedily for
k = 1is not needed — the rotations are the whole search space. - For
k >= 2the answer does not depend onkat all. - In C#, compare strings ordinally, not with culture-aware comparison.
Reference solution
Python
def orderlyQueue(s: str, k: int) -> str:
if k > 1:
return "".join(sorted(s))
return min(s[i:] + s[:i] for i in range(len(s)))Java
public static String orderlyQueue(String s, int k) {
if (k > 1) {
char[] a = s.toCharArray();
Arrays.sort(a);
return new String(a);
}
String best = s;
for (int i = 1; i < s.length(); i++) {
String cand = s.substring(i) + s.substring(0, i);
if (cand.compareTo(best) < 0) best = cand;
}
return best;
}C++
string orderlyQueue(string s, int k) {
if (k > 1) {
sort(s.begin(), s.end());
return s;
}
string best = s;
for (size_t i = 1; i < s.size(); i++) {
string cand = s.substr(i) + s.substr(0, i);
if (cand < best) best = cand;
}
return best;
}JavaScript
var orderlyQueue = function(s, k) {
if (k > 1) return s.split("").sort().join("");
var best = s;
for (var i = 1; i < s.length; i++) {
var cand = s.slice(i) + s.slice(0, i);
if (cand < best) best = cand;
}
return best;
};Also on the editorial tab: C, C#, Go, Kotlin, PHP, Ruby, Rust, Swift, TypeScript.
All 515 strings problems · the whole catalogue
Learn the technique: Strings · Sorting Algorithms