Sponsored
Sponsored
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.
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.
1#include <iostream>
2#include <string>
3#include <algorithm>
4
5std::string orderlyQueue(std::string s, int k) {
6 if (k > 1) {
7 std::sort(s.begin(), s.end());
8 return s;
9 }
10 std::string result = s;
11 for (int i = 1; i < s.length(); ++i) {
12 std::string t = s.substr(i) + s.substr(0, i);
13 if (t < result) {
14 result = t;
15 }
16 }
17 return result;
18}
19
20int main() {
21 std::string s = "cba";
22 int k = 1;
23 std::cout << orderlyQueue(s, k) << std::endl;
24 return 0;
25}This C++ solution uses similar logic: If k > 1, the string is sorted to get the smallest permutation. When k == 1, it rotates the string to find the smallest lexicographic order by comparing all rotations.
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.
Time Complexity: O(n log n) due to sorting.
Space Complexity: O(n) for holding the sorted version of the string.
1
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.