DEV Community

codingpineapple
codingpineapple

Posted on

LeetCode 791. Custom Sort String (javascript solution)

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;
};
Enter fullscreen mode Exit fullscreen mode

Top comments (0)