451. Sort Characters By Frequency

Sort Characters By Frequency

Problem Description

Given a string s, sort it in decreasing order based on the frequency of the characters. The frequency of a character is the number of times it appears in the string.

Return the sorted string. If there are multiple answers, return any of them.

 

Example 1:

Input: s = "tree"
Output: "eert"

Explanation: 'e' appears twice while 'r' and 't' both appear once.
So 'e' must appear before both 'r' and 't'. Therefore "eetr" is also a valid answer.

Example 2:

Input: s = "cccaaa"
Output: "aaaccc"

Explanation: Both 'c' and 'a' appear three times, so both "cccaaa" and "aaaccc" are valid answers.
Note that "cacaca" is incorrect, as the same characters must be together.

Example 3:

Input: s = "Aabb"
Output: "bbAa"

Explanation: "bbaA" is also a valid answer, but "Aabb" is incorrect.
Note that 'A' and 'a' are treated as two different characters.

 

Constraints:

• 1 <= s.length <= 5 * 105
• s consists of uppercase and lowercase English letters and digits.

Approach) Hashtable

/**
 * @param {string} s
 * @return {string}
 */
var frequencySort = function(s) {
    stringAsObj = {};
    
    //Typical object key value pairs hashmap
    for(let item of s){
        if(!stringAsObj[item])
            stringAsObj[item] = 0;
        stringAsObj[item]++;
    }
    //Cool, we are able to sort values of an object in javascript with object keys getting the list of index/key and sort based on that b - a => descending order
    let sortedString = Object.keys(stringAsObj).sort(function(a,b){ return stringAsObj[b] -        stringAsObj[a]})
    
    let result = "";
    for(let item of sortedString){
        // repeat is a method where you input the number of occurrence. We just concatenate to result
        result = result + item.repeat(stringAsObj[item])
    }
   
    return result;
};

Approach) Another Hashtable

var frequencySort = function(s) {
    let length = s.length;
    let alphabet = new Array(127).fill(0);
    let max = 0;
    let hash;
    for (let i = 0; i < length; i++) {
        alphabet[s.charCodeAt(i)] += 1;
        max = Math.max(max, alphabet[s.charCodeAt(i)]);
    };
    hash = new Array(max + 1).fill('');
    for (let i = 0; i < 127; i++) {
        let val = alphabet[i];
        hash[max - val] += String.fromCharCode(i).repeat(val);
    };
    return hash.join('');
};

Approach) Bucket Sort

var frequencySort = function(s) {
    let counts = new Map();
    
    for (const char of s) {
        if (!counts.has(char)) counts.set(char, 0);
        counts.set(char, counts.get(char) + 1);
    }
    
    const buckets = new Array(s.length);
    
    for (let i = 0; i <= s.length; i++) {
        buckets[i] = [];
    }
    
    for (const [char, count] of counts) {
        buckets[count].push(char);
    }
    
    let str = "";
    
    for (let i = buckets.length - 1; i >= 0; i--) {
        while (buckets[i].length > 0) {
            const char = buckets[i].pop();
            str += char.repeat(i);
        }
      
    }
    
    return str;
};

Approach) Short Using Javascript In-Built Method

/**
 * @param {string} s
 * @return {string}
 */
const frequencySort = s =>
  Object.entries(s.split('').reduce((prev, c) => ((prev[c] = (prev[c] || 0) + 1) && prev), {}))
    .sort(([, a], [, b]) => b - a)
    .reduce((res, [k, v]) => res + k.repeat(v), '');




Approach) Using Javascript In-Built Method

var frequencySort = function(s) {
    
    const charMap = s.split('').reduce((acc, cur) => {acc[cur] = (acc[cur] || 0) + 1; return acc} , {})
    
    const sortedArr = Object.keys(charMap).sort((a, b) => charMap[b] - charMap[a]);
    
    return sortedArr.reduce((acc, cur) => acc + cur.repeat(charMap[cur]) ,'')
};

Approach) Heap - Max Priority Queue

var frequencySort = function(s) {
    var table = {};
    var res = []; 
    var q = new MaxPriorityQueue(); 
    for (var c of s){
        if (!(c in table)) table[c] = 0;
        table[c]++; 
    };
    for (var char in table){
       q.enqueue(char, table[char]);
    }; 

    while(q.size()){
      var {priority, element} = q.dequeue(); 
      var str = element.repeat(priority);
        res.push(str); 
    };
    
    return res.join('');
};

Conclusion

That’s all folks! In this post, we solved LeetCode problem 451. Sort Characters By Frequency

I hope you have enjoyed this post. Feel free to share your thoughts on this.

You can find the complete source code on my GitHub repository. If you like what you learn. feel free to fork 🔪 and star ⭐ it.

In this blog, I have tried to collect & present the most important points to consider when improving Data structure and logic, feel free to add, edit, comment, or ask. For more information please reach me here
Happy coding!