loading...

Sorting Characters in a String By Their Frequency

alisabaj profile image Alisa Bajramovic Updated on ・3 min read

Algorithm of the Day (40 Part Series)

1) The Happy Number Problem 2) Kadane's Algorithm & The Maximum Subarray Problem 3 ... 38 3) Finding the Only Single Number in an Array 4) Finding the Middle of a Linked List 5) Backspace String Comparisons: Two Ways To Approach a Common Algorithm 6) The Stock Span Problem: Using Stacks To Keep Track Of What's Been Seen 7) Finding the Kth Smallest Element: Walking Through How To Use Depth First Search on a Binary Search Tree 8) The Boyer-Moore Majority Vote Algorithm: Finding the Majority Element in an Array 9) Sorting Characters in a String By Their Frequency 10) Finding the Intersection of Two Arrays 11) Finding the Minimum Path Sum in a Grid with Dynamic Programming 12) Floyd's Tortoise and Hare Algorithm: Finding a Cycle in a Linked List 13) The Sieve of Eratosthenes: Counting the Number of Primes 14) Add Two Numbers Problems: How to Sum Two Linked Lists 15) The Longest Substring With No Repeating Characters 16) Merging Sorted Lists, Two Ways 17) Finding the Longest Common Prefix 18) Reversing a String in Place 19) The ZigZag Conversion Problem 20) The Longest Palindromic Substring: Solving the Problem Using Constant Space 21) Removing an Element in an Array In-Place 22) Solving the Best Time to Buy and Sell Stocks Problem in One Pass 23) Don't Underestimate the Two Pointers: Removing the N-th Node from the End of a Linked List 24) Not an "Easy" Algorithm: Rotating an Array, Three Ways 25) Sudoku Part I: Is the Board Valid? 26) Searching an Array, Two Ways 27) The Climbing Staircase Problem: How to Solve It, and Why the Fibonacci Numbers are Relevant 28) Transposing and Reversing: How to Rotate a 2D Matrix 90 Degrees 29) Turning 38 into 2: How to Solve the Add Digits Problem 30) The Gauss Sum, and Solving for the Missing Number 31) Is this Number the Sum of Two Square Integers? Solving The Sum of Squares Algorithm Two Ways 32) The Word Pattern Algorithm: How to Test if a String Follows a Pattern 33) Finding the Intersection of Two Arrays 34) Top Interview Question: Finding the First Unique Character in a String using Linear Time 35) Solving Pascal's Triangle in JavaScript 36) The Maximum Number of Events Problem 37) Solving Binary Tree Algorithms Using Recursion and Queues 38) From "hello world" to "world hello": Reversing the Words in a String 39) Finding the Most Frequent Elements in an Array 40) Finding the Angle Between the Hands of a Clock

Today's algorithm is:

given a string, sort it in decreasing order based on the frequency of characters.

For example, if you were given the string "tree", the output could be either "eert" or "eetr". If you were given the string "Aabb", the output would be either "bbAa" or "bbaA" (note that "a" and "A" are treated as two different characters.

My initial feeling when I saw this problem was to use a hash map, storing the characters of the string as the keys, and their frequency as values. Then, to build an array of the keys, sorting them by their frequency. And finally, to build a new string, adding characters to it based on the sorted array.

To start this approach, I'll create a hash map, and then I'll loop through the characters of the string and insert them into the hash. If the character has already been seen in the string, I'll increment its value by 1; otherwise, I'll initialize it to equal 1.

function frequencySort(s) {
  let hash = {};
  for (let char of s) {
    if (hash[char]) {
      hash[char]++;
    } else {
      hash[char] = 1;
    }
  }
  //...
}

If the inputted string was "apple", the hash we would have right now would be {"a": 1, "p": 2, "l": 1, "e": 1}. From that hash, we now want to build an array of all of the different keys in the hash. We can easily do that using Object.keys().

function frequencySort(s) {
  let hash = {};
  for (let char of s) {
    if (hash[char]) {
      hash[char]++;
    } else {
      hash[char] = 1;
    }
  }
  let keys = Object.keys(hash);
  //...
}

Now, with the inputted string "apple", keys would equal ["a", "p", "l", "e"]. In order to sort these keys, we'll have to reference their values in the hash. To sort an array using .sort() in a decreasing order, we'll want to write a compare function where larger numbers go to the front.

function frequencySort(s) {
  let hash = {};
  for (let char of s) {
    if (hash[char]) {
      hash[char]++;
    } else {
      hash[char] = 1;
    }
  }
  let keys = Object.keys(hash);
  keys.sort((a, b) => hash[b] - hash[a]);
  //...
}

Now, continuing with the example of "apple", keys would equal ["p", "a", "l", "e"]. At the end of the problem we'll want to return a string, so we can initiate an empty string, and include a line to return the string at the bottom of the function.

function frequencySort(s) {
  let hash = {};
  for (let char of s) {
    if (hash[char]) {
      hash[char]++;
    } else {
      hash[char] = 1;
    }
  }
  let keys = Object.keys(hash);
  keys.sort((a, b) => hash[b] - hash[a]);
  let str = "";
  //...
  return str;
}

Now, the only remaining thing to do is to go through each element in keys and add it to str. However, we want to add each element the number of times that it's found in the hash. There are a number of ways to do this--one of which is to have a counter and a while loop, which I'll do here. As long as the counter is less than the the value of the key in the hash, the key gets added to the string.

function frequencySort(s) {
  let hash = {};
  for (let char of s) {
    if (hash[char]) {
      hash[char]++;
    } else {
      hash[char] = 1;
    }
  }
  let keys = Object.keys(hash);
  keys.sort((a, b) => hash[b] - hash[a]);
  let str = "";
  keys.forEach((k) => {
    let count = 0;
    while (count < hash[k]) {
      str += k;
      count++;
    }
  });
  return str;
}

So, if the input were "apple", the output of this function would be "ppale". I know there are other ways to approach this problem, so feel free to post your favorite approaches in the comments!

Algorithm of the Day (40 Part Series)

1) The Happy Number Problem 2) Kadane's Algorithm & The Maximum Subarray Problem 3 ... 38 3) Finding the Only Single Number in an Array 4) Finding the Middle of a Linked List 5) Backspace String Comparisons: Two Ways To Approach a Common Algorithm 6) The Stock Span Problem: Using Stacks To Keep Track Of What's Been Seen 7) Finding the Kth Smallest Element: Walking Through How To Use Depth First Search on a Binary Search Tree 8) The Boyer-Moore Majority Vote Algorithm: Finding the Majority Element in an Array 9) Sorting Characters in a String By Their Frequency 10) Finding the Intersection of Two Arrays 11) Finding the Minimum Path Sum in a Grid with Dynamic Programming 12) Floyd's Tortoise and Hare Algorithm: Finding a Cycle in a Linked List 13) The Sieve of Eratosthenes: Counting the Number of Primes 14) Add Two Numbers Problems: How to Sum Two Linked Lists 15) The Longest Substring With No Repeating Characters 16) Merging Sorted Lists, Two Ways 17) Finding the Longest Common Prefix 18) Reversing a String in Place 19) The ZigZag Conversion Problem 20) The Longest Palindromic Substring: Solving the Problem Using Constant Space 21) Removing an Element in an Array In-Place 22) Solving the Best Time to Buy and Sell Stocks Problem in One Pass 23) Don't Underestimate the Two Pointers: Removing the N-th Node from the End of a Linked List 24) Not an "Easy" Algorithm: Rotating an Array, Three Ways 25) Sudoku Part I: Is the Board Valid? 26) Searching an Array, Two Ways 27) The Climbing Staircase Problem: How to Solve It, and Why the Fibonacci Numbers are Relevant 28) Transposing and Reversing: How to Rotate a 2D Matrix 90 Degrees 29) Turning 38 into 2: How to Solve the Add Digits Problem 30) The Gauss Sum, and Solving for the Missing Number 31) Is this Number the Sum of Two Square Integers? Solving The Sum of Squares Algorithm Two Ways 32) The Word Pattern Algorithm: How to Test if a String Follows a Pattern 33) Finding the Intersection of Two Arrays 34) Top Interview Question: Finding the First Unique Character in a String using Linear Time 35) Solving Pascal's Triangle in JavaScript 36) The Maximum Number of Events Problem 37) Solving Binary Tree Algorithms Using Recursion and Queues 38) From "hello world" to "world hello": Reversing the Words in a String 39) Finding the Most Frequent Elements in an Array 40) Finding the Angle Between the Hands of a Clock

Posted on by:

alisabaj profile

Alisa Bajramovic

@alisabaj

Hi! I'm a software engineer with a background in social history.

Discussion

markdown guide