Sort Characters By Frequency

Leetcode Problem 451: Sort Characters By Frequency

Problem Summary

Given a string s, sort its characters in decreasing order of frequency and return the result. Characters with equal frequency can appear in any relative order.

Constraints:

• The string has between 1 and 500,000 characters.
• It consists of uppercase and lowercase English letters, and digits.

Techniques

• Hash Table
• String
• Sorting
• Heap (Priority Queue)
• Bucket Sort
• Counting

Solution

function frequencySort(s: string): string {
    let frequencies = new Map<string, number>()

    for (let i = 0; i < s.length; i++) {
        let currentChar = s.charAt(i)
        frequencies.set(currentChar, (frequencies.get(currentChar) || 0) + 1)
    }

    let bucketsOfFrequencies = new Map<number, string[]>()

    for (const [char, frequency] of frequencies) {
        let bucket = bucketsOfFrequencies.get(frequency) || []
        bucket.push(char)
        bucketsOfFrequencies.set(frequency, bucket)
    }

    let result = ""

    let sortedFrequencies = Array.from(bucketsOfFrequencies.keys()).sort((a, b) => b - a);

    for (const frequency of sortedFrequencies) {
        const chars = bucketsOfFrequencies.get(frequency)!;
        for (const currentChar of chars) {
            result += currentChar.repeat(frequency);
        }
    }

    return result
};


console.log(frequencySort("Aabb"))