Description:
order and str are strings composed of lowercase letters. In order, no letter occurs more than once.
order was sorted in some custom order previously. We want to permute the characters of str so that they match the order that order was sorted. More specifically, if x occurs before y in order, then x should occur before y in the returned string.
Return any permutation of str (as a string) that satisfies this property.
Solution:
Time Complexity : O(n)
Space Complexity: O(n)
var customSortString = function (order, str) {
const map = new Map();
// Count chars in str and save into map
for(let i=0;i<str.length;i++){
map.set(str[i],map.get(str[i])+1||1);
}
let res=''
// Add characters common between str and order to the res string
for(let i=0;i<order.length;i++){
res += order[i].repeat(map.get(order[i]))
map.delete(order[i])
}
// Add characters from str not found in order to the res string
for(let [key,value] of map){
if(value>0){
res+= key.repeat(value);
map.delete(key)
}
}
return res;
};
Top comments (0)