Approach 1: Using custom sort comparator
The question can easily be solved by assigning a number (hashmap used) to each character in S. If a character comes earlier in S then it is assigned a smaller number. T can be sorted easily using the built in sort() function using this hashmap. Below implementation uses a lambda comparator.
string customSortString(string S, string T) {
unordered_map<char, int> dir;
for (int i = 0; i < S.size(); i++) {
dir[S[i]] = i + 1;
}
sort(T.begin(), T.end(),
[dir](char a, char b) { return dir[a] < dir[b]; });
return T;
}
Time complexity: O(nlogn)
Although this approach is pretty intuitive and quick to implement, it does not leverage the given constraints and hence the time is not that good. We can solve the question in linear time. Especially, if size(T)»size(S), the next approach shown will work like a charm.
Approach 2: Bucket sort
The question mentions that S and T only have small letters. We can create a count array of size 26 and store the count of each letter in T in that array. Then for each char c in S, we can put c in our resulting resulting string count[c] number of times and decrease its count to 0. Then we can add the left over characters (count>0) in the result in any order.
string customSortString(string S, string T) {
vector<int> v(26, 0);
for (char c : T)
v[c-'a']++;
string res = "";
for (char c : S) {
for (int i=0; i<v[c-'a']; i++)
res+=c;
v[c-'a']=0;
}
for (int i=0; i<v.size(); i++) {
if (!v[i])
continue;
for (int j=0; j<v[i]; j++)
res+='a'+i;
}
return res;
}
Time complexity: O(n)