Orderly Queue Problem
Description
LeetCode Problem 899.
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:
1
2
3
4
5
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:
1
2
3
4
5
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.
Sample C++ Code
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
class Solution {
public:
// If k==1, then we can only choose the first letter and append it to the end.
// This is basically rotating the string. So we can just try rotating and see the smallest result.
// If k>1, then we can do some amount of moves to always get the string sorted.
// We can keep 1 or more numbers in the beginning of the string and take care only of the rest.
string orderlyQueue(string s, int k) {
if (k > 1) {
sort(s.begin(), s.end());
return s;
}
string res = s;
for (int i = 0; i < s.size(); i++)
res = min(res, s.substr(i)+s.substr(0, i));
return res;
}
};