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.
1function customSortString(order, s) {
2 let count = {};
3 for (let char of s) {
4 count[char] = (count[char] || 0) + 1;
5 }
6
7 let result = '';
8 for (let char of order) {
9 if (count[char]) {
10 result += char.repeat(count[char]);
11 delete count[char];
12 }
13 }
14
15 for (let char in count) {
16 result += char.repeat(count[char]);
17 }
18
19 return result;
20}
21
22let order = "cba";
23let s = "abcd";
24console.log(customSortString(order, s));This JavaScript solution uses an object to store frequencies of characters in s. The order string is used to append matching characters to the result string. Finally, any remaining characters in s are added to the result.
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.