Watch 10 video solutions for Orderly Queue, a hard level problem involving Math, String, Sorting. This walkthrough by codestorywithMIK has 15,114 views views. Want to try solving it yourself? Practice on FleetCode or read the detailed text solution.
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 <= 1000s consist of lowercase English letters.Problem Overview: You are given a string s and an integer k. In one move, you can choose one of the first k characters and move it to the end of the string. The goal is to produce the lexicographically smallest string possible after any number of moves.
Approach 1: Rotational Minimization (O(n^2) time, O(1) space)
When k == 1, you are restricted to moving only the first character to the end. That operation is equivalent to performing a rotation of the string. Because every move shifts the first character to the back, the only strings you can generate are the n cyclic rotations of the original string. The strategy is simple: generate each rotation s[i:] + s[:i] and track the lexicographically smallest one using standard string comparison. Each comparison takes up to O(n), and there are n rotations, giving O(n^2) total time. This approach relies purely on string manipulation and lexicographic ordering.
Approach 2: Direct Sorting (Applicable for k > 1) (O(n log n) time, O(n) space)
When k > 1, the problem changes completely. You can choose any of the first two characters and move it to the end, which effectively allows adjacent swaps after a sequence of operations. With enough moves, this gives you the freedom to reorder characters arbitrarily. Once arbitrary permutations are reachable, the smallest possible string is simply the sorted version of the characters. Convert the string to a character array, sort it using a standard sorting algorithm, and join the result. Sorting takes O(n log n) time and O(n) space depending on the implementation. This approach relies on concepts from sorting and reasoning about reachable permutations using simple math observations.
Recommended for interviews: Interviewers expect you to recognize the key observation that the value of k changes the reachable state space. Demonstrating the rotation-based reasoning for k == 1 shows you understand the constraint. Identifying that k > 1 enables arbitrary reordering and immediately switching to sorting shows strong problem reduction skills. The optimal interview solution combines both insights in a simple conditional.
| Approach | Time | Space | When to Use |
|---|---|---|---|
| Rotational Minimization (k = 1) | O(n^2) | O(1) | When only cyclic rotations are possible and k equals 1 |
| Direct Sorting (k > 1) | O(n log n) | O(n) | General case when k is greater than 1 and arbitrary permutations become reachable |