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.
1using System;
2using System.Text;
3using System.Collections.Generic;
4
5class CustomSortStringClass {
6 public string CustomSortString(string order, string s) {
7 Dictionary<char, int> countMap = new Dictionary<char, int>();
8 foreach (char c in s) {
9 if (countMap.ContainsKey(c))
10 countMap[c]++;
11 else
12 countMap[c] = 1;
13 }
14
15 StringBuilder result = new StringBuilder();
16 foreach (char c in order) {
17 if (countMap.ContainsKey(c)) {
18 result.Append(c, countMap[c]);
19 countMap.Remove(c);
20 }
21 }
22
23 foreach (var item in countMap) {
24 result.Append(item.Key, item.Value);
25 }
26
27 return result.ToString();
28 }
29
30 static void Main() {
31 CustomSortStringClass css = new CustomSortStringClass();
32 string order = "cba";
33 string s = "abcd";
34 Console.WriteLine(css.CustomSortString(order, s));
35 }
36}In this C# implementation, a Dictionary counts character occurrences in string s. Using a StringBuilder, it builds the result string by following the sequence specified in order. Characters in s not in order are appended subsequently.
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.