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.
This approach is best when k = 1. Since you can only move the first character to the end, you are only able to produce rotations of the string. Therefore, to find the lexicographically smallest string, you can generate all rotations of the string and find the smallest one.
In this C implementation, rotateString is a helper function to get a rotated version of the string. The main function checks if k > 1 to sort the string. If k == 1, it rotates the string in all possible ways and keeps track of the lexicographically smallest string. The qsort function from the standard library sorts the string when k > 1.
Time Complexity: O(n^2), where n is the length of the string for k = 1 due to generating all rotations.
When k > 1, Time Complexity: O(n log n) due to sorting.
Space Complexity: O(n) for holding copies of the string during rotations or sorting.
When k > 1, the problem allows moving any of the top k characters to the end, meaning we can potentially rearrange the entire string. Thus, this is equivalent to sorting the characters in the string to achieve the lexicographically smallest string. This can be directly achieved by sorting the string.
This C solution employs qsort to sort the characters of the string when k > 1. For this approach, when k==1, it is assumed to be handled by another approach since the logic for k=1 isn't applicable here.
Time Complexity: O(n log n) due to sorting.
Space Complexity: O(n) for holding the sorted version of the string.
If k = 1, we can only move the first character of the string to the end of the string each time, resulting in |s| different states. We return the string with the smallest lexicographic order.
If k > 1, for a string like abc[xy]def, we can move a, b, and c to the end in order, resulting in [xy]defabc. Then we move y and x to the end, resulting in defabc[yx]. Finally, we move d, e, and f to the end, resulting in abc[yx]def. This way, we have swapped y and x.
Therefore, as long as k > 1, we can swap any two adjacent characters in the string, eventually obtaining a string sorted in ascending order.
The time complexity is O(n^2), and the space complexity is O(n). Here, n is the length of the string.
Python
Java
C++
Go
TypeScript
| Approach | Complexity |
|---|---|
| Approach 1: Rotational Minimization | Time Complexity: O(n^2), where n is the length of the string for k = 1 due to generating all rotations. |
| Approach 2: Direct Sorting (Applicable for k > 1) | Time Complexity: O(n log n) due to sorting. |
| Case-by-case Judgment | — |
| 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 |
Orderly Queue -(Amazon): Explanation ➕ Live Coding • codestorywithMIK • 15,114 views views
Watch 9 more video solutions →Practice Orderly Queue with our built-in code editor and test cases.
Practice on FleetCodePractice this problem
Open in Editor