Sort Characters By Frequency

Problem Statement

Constraints

Solution 1: Frequency Sort Using Object Counting and Custom Sorting

function frequencySortCustomSort(inputString) {
    // Count the frequency of each character
    const characterFrequency = {};
    for (const character of inputString) {
        characterFrequency[character] = (characterFrequency[character] || 0) + 1;
    }

    // Sort characters by frequency in descending order and then by character
    const sortedCharacters = Object.entries(characterFrequency).sort((a, b) => {
        if (b[1] === a[1]) {
            return a[0].localeCompare(b[0]); // Sort alphabetically if frequencies are the same
        }
        return b[1] - a[1]; // Sort by frequency
    });

    // Build the result string by repeating characters according to their frequency
    let sortedString = '';
    for (const [character, frequency] of sortedCharacters) {
        sortedString += character.repeat(frequency);
    }

    return sortedString;
} 

const string1 = "tree";
frequencySortCustomSort(string1);  //output: eert 

const string2 = "cccaaa";
frequencySortCustomSort(string2);  //output: aaaccc 

const string3 = "Aabb";
frequencySortCustomSort(string3);  //output: bbaA 

Solution 2: Frequency Sort via Counting and Sorting Algorithm

function frequencySortCounting(inputString) {
  // Create a Map to store character frequencies
  let characterFrequencies = new Map();

  // Count the frequency of each character
  for (let character of inputString) {
    characterFrequencies.set(
      character,
      (characterFrequencies.get(character) ?? 0) + 1
    );
  }

  // Sort characters by frequency and build the output string
  let sortedOutput = [...characterFrequencies.entries()]
    .sort((a, b) => b[1] - a[1]) // Sort by frequency in descending order
    .map((entry) => entry[0].repeat(entry[1])) // Repeat characters according to their frequency
    .join(""); // Join the array into a single string

  return sortedOutput;
}; 

const string1 = "tree";
frequencySortCounting(string1);  //output: eert 

const string2 = "cccaaa";
frequencySortCounting(string2);  //output: aaaccc 

const string3 = "Aabb";
frequencySortCounting(string3);  //output: bbaA 

Solution 3: Frequency Sort Using a Priority Queue

function frequencySortPriorityQueue(inputString) {
    let sortedResult = "";
    let characterCountMap = new Map();
    
    // Count the frequency of each character
    for (let i = 0; i < inputString.length; i++) {
        characterCountMap.set(inputString[i], (characterCountMap.get(inputString[i]) || 0) + 1);
    }

    let characterArray = [...characterCountMap.entries()];
    // Sort the array using a priority queue
    let priorityQueue = new PriorityQueue();
    for (let i = 0; i < characterArray.length; i++) {
        priorityQueue.enqueue(characterArray[i][0], characterArray[i][1]);
    }
    characterArray = priorityQueue.getQueue();

    // Build the result string based on frequencies
    for (let i = characterArray.length - 1; i >= 0; i--) {
        let frequency = characterArray[i].frequency;
        while (frequency) {
            sortedResult += characterArray[i].character;
            frequency -= 1;
        }
    }

    return sortedResult;
};

class QueueElement {
    constructor(character, frequency) {
        this.character = character;
        this.frequency = frequency;
    }
}

class PriorityQueue {
    constructor() {
        this.elements = [];
    }

    enqueue(character, frequency) {
        let queueElement = new QueueElement(character, frequency);
        let inserted = false;
        for (let i = 0; i < this.elements.length; i++) {
            if (this.elements[i].frequency > queueElement.frequency) {
                this.elements.splice(i, 0, queueElement);
                inserted = true;
                break;
            }
        }

        if (!inserted) {
            this.elements.push(queueElement);
        }
    }

    getQueue() {
        return this.elements;
    }
} 

const string1 = "tree";
frequencySortPriorityQueue(string1);  //output: eert 

const string2 = "cccaaa";
frequencySortPriorityQueue(string2);  //output: aaaccc 

const string3 = "Aabb";
frequencySortPriorityQueue(string3);  //output: bbaA 

Solution 4: Frequency Count and Bitwise Encoding Approach for Character Sorting

function frequencySortBitwise(s) {
    const freq = new Array(75).fill(0);

    for (const char of s) {
        const code = char.charCodeAt(0) - 48;
        freq[code] = ((freq[code] >> 7) + 1) << 7 | code;
    }

    // Sort the array in descending order
    freq.sort((a, b) => b - a);

    let result = '';
    for (const v of freq) {
        if (v > 0) { // Only process non-zero frequencies
            const count = v >> 7; // Extract frequency
            const char = String.fromCharCode((v & 127) + 48); // Extract character
            result += char.repeat(count); // Repeat the character by its frequency
        }
    }

    return result;
} 

const string1 = "tree";
frequencySortBitwise(string1);  //output: eert 

const string2 = "cccaaa";
frequencySortBitwise(string2);  //output: aaaccc 

const string3 = "Aabb";
frequencySortBitwise(string3);  //output: bbaA 

Solution 5: Merge Sort-Based Character Frequency Sorter in JavaScript

function frequencySortMergeSort(s) {
    const N = 63;
    const map = new Array(N).fill(0).map(() => ({ val: '', f: 0 }));

    // Count frequencies
    for (const char of s) {
        let index;
        if (char >= 'A' && char <= 'Z') {
            index = char.charCodeAt(0) - 'A'.charCodeAt(0) + 10; // 10-35 for uppercase
        } else if (char >= 'a' && char <= 'z') {
            index = char.charCodeAt(0) - 'a'.charCodeAt(0) + 36; // 36-61 for lowercase
        } else {
            index = char.charCodeAt(0) - '0'.charCodeAt(0); // 0-9 for digits
        }
        map[index].val = char;
        map[index].f++;
    }

    // Merge sort function
    function merge(A, B, l, r, c) {
        let i = l, j = c + 1, k = l;

        while (i <= c && j <= r) {
            if (A[i].f <= A[j].f) {
                B[k++] = A[i++];
            } else {
                B[k++] = A[j++];
            }
        }

        while (i <= c) B[k++] = A[i++];
        while (j <= r) B[k++] = A[j++];

        for (let m = l; m <= r; m++) {
            A[m] = B[m];
        }
    }

    function mergeSort(A, B, l, r) {
        if (r <= l) return;
        const c = Math.floor((l + r) / 2);
        mergeSort(A, B, l, c);
        mergeSort(A, B, c + 1, r);
        merge(A, B, l, r, c);
    }

    const B = new Array(N);
    mergeSort(map, B, 0, N - 1);

    // Build the result string
    let result = '';
    for (let i = N - 1; map[i].f > 0; i--) {
        result += map[i].val.repeat(map[i].f);
    }

    return result;
} 

const string1 = "tree";
frequencySortMergeSort(string1);  //output: eert 

const string2 = "cccaaa";
frequencySortMergeSort(string2);  //output: aaaccc 

const string3 = "Aabb";
frequencySortMergeSort(string3);  //output: bbaA 

Resources

Frequently asked questions

1. What is the main objective of the Sort Characters By Frequency problem?

   The objective is to sort the characters of a given string in decreasing order of their frequency of occurrence. Characters that appear more often should appear earlier in the result string.

2. What should I do if two characters have the same frequency?

   f two characters have the same frequency, their relative order in the output can be arbitrary. You can choose either character to come first.

3. Are uppercase and lowercase characters treated the same?

   No, uppercase and lowercase characters are treated as distinct characters. For example, 'A' and 'a' are considered different characters with their own frequencies.

4. What are some common approaches to solve this problem?

   Common approaches include:

   • Counting character frequencies using a hash map and then sorting them.

   • Using a priority queue to manage characters based on their frequencies.

   • Implementing custom sorting algorithms like merge sort or quick sort.

More Problems Solutions