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.
1from collections import Counter
2
3def customSortString(order: str, s: str) -> str:
4 count = Counter(s)
5 result = []
6
7 for char in order:
8 if char in count:
9 result.append(char * count[char])
10 del count[char]
11
12 for char, cnt in count.items():
13 result.append(char * cnt)
14
15 return ''.join(result)
16
17order = "cba"
18s = "abcd"
19print(customSortString(order, s))This Python solution uses the Counter class to store character frequencies from s. It builds the result string using characters from order, then adds any leftover characters from s. Finally, it joins the list of characters into a string.
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.