Orderly Queue

Hard
1459.

Orderly Queue

Orderly Queue is a hard coding problem on strings, math and sorting, asked in Amazon and Google interviews.

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 <= 1000
  • s consists of lowercase English letters
Write your solution here. Running it against the tests needs a free account — what you type comes with you.Sign in to run
/**
 * @param {string} s
 * @param {number} k
 * @return {string}
 */
var orderlyQueue = function(s, k) {
    // Write your code here
    
};

Sign in to run your own test cases

Sign in

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 <= 1000
  • s consists of lowercase English letters

Hints for Orderly Queue

  1. Hint 1

    With k = 1 each move rotates the string by one position, so the reachable strings are exactly the rotations.

  2. Hint 2

    With k = 2 you can hold one letter back while the rest rotate past it — that lets you swap two adjacent letters.

  3. Hint 3

    Adjacent swaps can sort anything, so for k >= 2 the 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

  1. If k == 1: compare all n rotations s[i:] + s[:i] and return the smallest.
  2. Otherwise return the letters of s in 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 = 1 is not needed — the rotations are the whole search space.
  • For k >= 2 the answer does not depend on k at 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