TL;DR
- Problems where you are counting frequencies often are great candidates to use the map data structure.
- We need to count the character frequencies, extrapolate the characters, sort the extrapolated strings, and then join these strings back together.
- This algorithm has
O(n*log(n)time complexity andO(n)space complexity.
Problem Description
Given a string
s, sort it in decreasing order based on the frequency of the characters. The frequency of a character is the number of times it appears in the string.Return the sorted string. If there are multiple answers, return any of them.
This problem comes from LeetCode. There is no shortage of practice problems out there, but LeetCode is one of the most popular platforms for honing your algorithm design skills. With practice problems, solutions, and a healthy user base to discuss problems with, LeetCode is a great resource.
Problem Solution
The key to this problem is to map the characters to the frequency in which they occur in the string. Whenever you encounter a problem where the word "frequency" is used, there's a good chance that a map will be the right tool for the job.
Once all of the characters are mapped, we need to extrapolate or individual characters into strings that contain the character repeated the proper number of times. We can then sort those strings and join them into one final string.
Let's break down the logic into smaller, digestible pieces.
Counting Characters
Rather than trying to inefficiently group and sort these characters in place, instead, it is much easier to simply count the character frequencies and then create the character groupings we'd like to see later. The map data structure is particularly useful here because it is implemented in a way that allows us to have constant time lookup (i.e. O(1)). So by using a map, when we want to add to a character's tally, it's a fast lookup to check if we already have that character in the map.
So, we can iterate through our characters and check if they already exist in our map. If they do, we'll increment the tally for that character by 1, and if not, we'll add that character to the map with an initial tally value of 1.
Extrapolating and Sorting
Extrapolating the character to a string comprised of the character repeated by its frequency could be its own section in this algorithm, but most mature programming languages have a built-in, declarative way to do this. In JavaScript, we can use String.prototype.repeat to accomplish this.
With the extrapolation logic already taken care of, our logic is as follows: iterate through the map, extrapolate the character, and push that extrapolated string into a sortable data structure, and then sort. The key here is to use an easily-sortable data structure. In JavaScript, arrays have a native Array.prototype.sort method that can be used to declaratively sort items, so we'll use one to store our extrapolated strings.
Joining
After we've sorted our strings, we simply need to join them together into our final result string. Once again, JavaScript has a declarative prototype method called Array.prototype.join that will do this for us. If you'd rather implement the joining logic yourself, you simply need to iterate through the array and concatenate each string to a result string.
JavaScript Implementation
Now that we have our mental model and algorithm in place, translating it to code is fairly trivial. Let's take a look at a JavaScript implementation.
As you can see, the mapping logic is implemented on lines 2 through 7. We create an empty object to act as our map, use a for loop to iterate through our string, and on each iteration we use basic object property assignment to update our character frequencies.
The character extrapolation happens on lines 9 through 14. You'll notice we use a for...in loop to iterate through our object, and on each iteration, we extrapolate our string using the String.prototype.repeat method and we push it to the end of our array. Afterward, we use Array.prototype.sort to sort our strings by length.
Finally, we use Array.prototype.join to combine our array of strings into one final string on line 17.
If you'd like to run this code, you can copy it from here.
Efficiency
An algorithm is only as good as its efficiency. An inefficient algorithm is certainly better than nothing during an interview, but typically the "brute force" approach is not going to cut it. So, it's important to understand how to calculate the efficiencies of your algorithm and how to communicate that information to others.
The efficiency of an algorithm is generally described using Big O Notation and is used to define both time complexity and space complexity.
Time Complexity
For our problem, the mapping is linear (i.e. O(n)) and so is the joining, but the bottleneck here is the sorting. The sorting efficiency depends on the implementation of the JavaScript runtime. Chrome uses the V8 engine, which itself implements Array.prototype.sort using the Timsort algorithm, which on average produces a time complexity of O(n*log(n)). Because these operations are sequential and not nested, the largest complexity dwarfs the others as n (the number of items in the data structure) approaches infinity.
Space Complexity
Inherently, the mapping operation takes up linear space (i.e. O(n)) because, for each character in our string, we are allocating a chunk of memory in our map. On average, the memory used in the mapping will be less n because we will often have repeat characters, but we're typically only concerned with worst-case scenarios in algorithm problems. The extrapolating portion is also linear because we're adding an item to our array for each entry in our map. These are the only two parts of the operation that consume additional memory, and since they are both linear, the algorithm as a whole is considered to have linear (i.e. O(n)) space complexity.
Conclusion
Algorithm problems are about recognizing when to use particular logic patterns. To do so, you need to familiarize yourself with the various patterns and combinations of patterns out there.
Mapping characters to the frequency in which they occur is a common pattern that you should become very familiar with. Once you fully understand the strategy and the efficiencies behind it, you'll start to recognize other areas where it can be properly used.