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 <stdio.h>
2#include <string.h>
3
4void rotateString(char *dest, const char *src, int start, int length) {
5 for (int i = 0; i < length; ++i) {
6 dest[i] = src[(start + i) % length];
7 }
8 dest[length] = '\0';
9}
10
11char* orderlyQueue(char* s, int k) {
12 if (k > 1) {
13 // Sort the characters
14 int len = strlen(s);
15 char *sorted = strdup(s);
16 qsort(sorted, len, sizeof(char), (int (*)(const void *, const void *)) strcmp);
17 return sorted;
18 } else {
19 int len = strlen(s);
20 char *minString = strdup(s);
21 char *current = (char *)malloc((len + 1) * sizeof(char));
22
23 for (int i = 1; i < len; ++i) {
24 rotateString(current, s, i, len);
25 if (strcmp(current, minString) < 0) {
26 strcpy(minString, current);
27 }
28 }
29
30 free(current);
31 return minString;
32 }
33}
34
35int main() {
36 char s[] = "cba";
37 int k = 1;
38 printf("%s\n", orderlyQueue(s, k));
39 return 0;
40}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.
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.
1using System;
using System.Linq;
public class OrderlyQueue {
public string OrderlyQueueMethod(string s, int k) {
if (k == 1) { return null; /* This approach doesn't handle k=1 */}
char[] arr = s.ToCharArray();
Array.Sort(arr);
return new string(arr);
}
public static void Main() {
OrderlyQueue solution = new OrderlyQueue();
string s = "baaca";
int k = 3;
Console.WriteLine(solution.OrderlyQueueMethod(s, k));
}
}In C#, we use Array.Sort() to sort the string when k > 1. The assumption is k = 1 is addressed in another part of the solution.