Sponsored
Sponsored
This approach involves counting the occurrence of each character in string s and then constructing the result string by iterating through characters in order, followed by any characters in s that do not appear in order. This ensures the output string follows the custom order defined.
Time Complexity: O(n + m), where n is the length of s and m is the length of order, since we iterate through each character of both strings.
Space Complexity: O(1), only a fixed extra space for the frequency array is used.
1#include <stdio.h>
2#include <string.h>
3
4char* customSortString(char* order, char* s) {
5 int freq[26] = {0};
6 for (int i = 0; s[i]; i++) {
7 freq[s[i] - 'a']++;
8 }
9
10 int idx = 0;
11 static char result[201];
12 for (int i = 0; order[i]; i++) {
13 while (freq[order[i] - 'a']-- > 0) {
14 result[idx++] = order[i];
15 }
16 }
17
18 for (int i = 0; i < 26; i++) {
19 while (freq[i]-- > 0) {
20 result[idx++] = 'a' + i;
21 }
22 }
23
24 result[idx] = '\0';
25 return result;
26}
27
28int main() {
29 char order[] = "cba";
30 char s[] = "abcd";
31 printf("%s\n", customSortString(order, s));
32 return 0;
33}The solution uses a frequency array to count occurrences of characters in string s. Next, it iterates through the custom order string order to construct part of the result by taking corresponding characters from s. Finally, any leftover characters from s are added to the result in their natural order.
This approach involves sorting the string s using a custom comparator function derived from the order string. You respect the sequence provided in order and sort the characters of s accordingly.
Time Complexity: O(n log n), due to the sorting operation.
Space Complexity: O(1) for map usage and additional space for sort function.
1#include <iostream>
2#include <string>
3#include <algorithm>
#include <unordered_map>
using namespace std;
string customSortString(string order, string s) {
unordered_map<char, int> priority;
for (int i = 0; i < order.size(); i++) {
priority[order[i]] = i;
}
sort(s.begin(), s.end(), [&](char a, char b) {
return priority[a] < priority[b];
});
return s;
}
int main() {
string order = "cba";
string s = "abcd";
cout << customSortString(order, s) << endl;
return 0;
}In this C++ solution, an unordered_map is used to assign indices as priorities based on order. The custom comparator used in the sort function rearranges s to fit these priorities.