911. Front-of-Queue Shuffle
Lowercase letters stand in a queue, given by the string s from front to back. In one move you pick any one of the first k letters of the queue (all of them if the queue is shorter than k), take it out of its place, and send it to the very back. You may make as many moves as you like, including none.
Return the lexicographically smallest string the queue can spell after some sequence of moves.
The state space is huge, so look for a pattern for small and large values of k. Aim for O(n) time, where n is the length of s, and at most O(n) extra space.
Example 1
- Input:
- s = "cbdab", k = 1
- Output:
- "abcbd"
- Explanation:
With
k= 1 the smallest reachable arrangement is \"abcbd\".
Example 2
- Input:
- s = "zgdcxy", k = 2
- Output:
- "cdgxyz"
- Explanation:
With
k= 2 the smallest reachable arrangement is \"cdgxyz\".
Constraints
1 ≤ s.length ≤ 105
1 ≤ k ≤ 109
s consists of lowercase English letters.
How this problem is judged
- Answers
- Your answer must match exactly. Numbers compare by value, so 2 and 2.0 are equal.
- Time per case
- Python 1,600 msC++ 400 msJava 800 msJavaScript 800 msTypeScript 800 ms
Expected complexity
- Time
- O(n)
- Space
- O(n)