Programming Exercise: Frequency Sort

programming-exercises (5 Part Series)

1 Leetcode: Integer to Roman
2 Leetcode Problem: Three sum
3 Leetcode Problem: Group Anagrams
4 Leetcode Problem: Valid Parenthesis
5 Programming Exercise: Frequency Sort

Background

Recently, I decided to solve some of the problems in leetcode.com for fun and practicing my java which I have not used in a while. I decided to document my thought process as I solve these problems. You can find some of the other solutions in the series table above this section.

Problem

Frequency Sort
Given a string, return another string where the characters are sorted by the frequency of their appearance with the most repeating at the beginning.
Eg:

Input: tree
Output: eert
Input: aabbbc
Output: bbbaac

Solution

Whenever I see a problem like this, where the output depends on the how each item in a list relate to another item in the list (here for e.g. how many times each element appears in the list) my mind immediately jumps to a two pass approach with a hashmap.

This is not because hashmaps are my favorite data structure (I don’t have a favorite data structure), but rather the ease of lookup of hashmaps. So usually my mind thinks how I can store the data in a hashmap in the first pass, so that I can look it up in the second pass thereby avoiding a nested loop.

This problem was no different and I started out the same way. But when I started to write down what the hashmap I needed I realized I might need two hashmaps. One to represent how many counts of a characters there are, and another to represent the different counts itself. (There might be a better way of doing it, but this is what I came up with in the first try)

So my two hashmaps for the second example above looked like this at the end of the first pass:

// For each character a string with their frequency
{
  a: aa,
  b: bbb,
  c: c
}
// For each count a list of characters with the count
{
  1: [a, b, c],
  2: [a, b],
  3: [b],
}

Now there is some repetition in the second map, but that was ok since I didn’t want to add additional complexity of lookup in the first pass.

From here it was a matter of sorting the counts and then forming a string from the other map.

This yielded the following code:

Complexity

Since there are a few different steps involved in here lets see the complexity of each step:

1. First pass – constructing the hashmap – O(n) where n is the length of the string.
2. Sorting the counts – O(k.log k) where k is the number of unique counts.
3. Second pass – constructing the result – 3.1 O(n) – if each character appeared only once. 3.2 O(k + n) – if there are k counts each with more than one item. But since k < n, that is really O(n)

So the most expensive operation here is the sort.

programming-exercises (5 Part Series)

1 Leetcode: Integer to Roman
2 Leetcode Problem: Three sum
3 Leetcode Problem: Group Anagrams
4 Leetcode Problem: Valid Parenthesis
5 Programming Exercise: Frequency Sort

原文链接：Programming Exercise: Frequency Sort