Is Orderly Queue easy or hard?

Orderly Queue is labeled Hard on LeetCode, but the implementation becomes simple once you identify the key observation about k. The difficulty comes from recognizing that k = 1 restricts operations to rotations, while k > 1 allows full reordering of characters.

Orderly Queue Python/Java solution

In Python or Java, the implementation is short. If k == 1, iterate through all rotations using substring operations and track the smallest string. If k > 1, convert the string to a character array, sort it using built-in sorting utilities, and return the joined result.

How to solve Orderly Queue in O(n)?

An O(n) theoretical solution exists for the k = 1 case using Booth's algorithm to find the lexicographically minimal rotation. However, most interview and competitive programming solutions simply check all rotations in O(n^2) because the constraints are small. For k > 1, sorting with O(n log n) is the standard approach.

What is the best approach for Orderly Queue?

The optimal approach depends on the value of k. If k = 1, only cyclic rotations of the string are possible, so you check all rotations and pick the lexicographically smallest in O(n^2) time. If k > 1, any permutation of the string becomes reachable, so sorting the characters directly in O(n log n) time produces the smallest possible string.

Is Orderly Queue asked at Google/Amazon/Meta?

Orderly Queue is a typical string manipulation and greedy reasoning problem similar to questions asked at companies like Amazon and Google. It tests understanding of lexicographic ordering, string rotations, and recognizing when constraints allow arbitrary permutations.

What data structure is used in Orderly Queue?

The solution primarily uses basic string operations and arrays of characters. For k = 1, you iterate through rotations and compare strings. For k > 1, the characters are placed in an array or list and sorted using a standard sorting algorithm.

What is the time complexity of Orderly Queue?

The complexity depends on the case. For k = 1, generating and comparing all rotations requires O(n^2) time and O(1) extra space. For k > 1, sorting the characters dominates the cost with O(n log n) time and O(n) space.

Description Solution Video 20:17

899. Orderly Queue

Hard67.4% acceptance2 companies

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 1^st character 'c' to the end, obtaining the string "bac".
In the second move, we move the 1^st 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 1^st character 'b' to the end, obtaining the string "aacab".
In the second move, we move the 3^rd character 'c' to the end, obtaining the final result "aaabc".

Constraints:

1 <= k <= s.length <= 1000
s consist of lowercase English letters.

Asked at 2 companies

Amazon Bloomberg

Topics

20:17

Still stuck?Read 3 approaches, or watch a walkthrough.

Open solution

LanguageLoading editor…

1class Solution:
2    def orderlyQueue(self, s: str, k: int) -> str:
3        

Starter codePython 3Spaces: 4

Examples

Case 1Case 2

Input

"cba"
1

Input

"baaca"
3

Your code is saved on this device.Solution