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.

Comments

[Anton Dreka]

That's my implementation with only one map:

private String sort(final String input) {
    char[] chars = input.toCharArray();
    Map<Character, String> map = new HashMap<>();
    for (int i = 0; i < chars.length; i++) {
        char charInMainIteration = chars[i];
        if (map.containsKey(charInMainIteration)) {
            continue;
        }

        StringBuilder repetitions = new StringBuilder(Character.toString(charInMainIteration));
        for (int j = i + 1; j < chars.length; j++) {
            if (charInMainIteration == chars[j]) {
                repetitions.append(charInMainIteration);
            }
        }

        map.put(chars[i], repetitions.toString());
    }

    StringBuilder result = new StringBuilder();
    map.values().stream()
            .sorted(Comparator.comparing(String::length).reversed())
            .forEach(result::append);

    return result.toString();
}

[Deepak Venkatachalam]

Thanks for sharing. That looks good. Question for you for my own clarification, isn't this n^2 steps because of the nested for loops each of n where n is the number of characters?

[Anton Dreka]

Yeah.
That's another way of doing it:

private String sort(final String input) {
    char[] chars = input.toCharArray();
    Map<Character, String> map = new HashMap<>();
    for (char c : chars) {
        map.put(c, map.containsKey(c) ? map.get(c) + c : Character.toString(c));
    }

    StringBuilder result = new StringBuilder();
    map.values().stream()
            .sorted(Comparator.comparing(String::length).reversed())
            .forEach(result::append);

    return result.toString();
}