In this article, I share only my thought process for day 5's Leetcode challenge for the #I4G10DaysOfCodeChallenge series. To curb the occurrence of plagiarism we've been advised to not share our solutions completely. I have never actually solved this problem on Leetcode before, so let's dive in.
Problem statement, examples, and constraints.
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.
Input: s = "tree" Output: "eert" Explanation: 'e' appears twice while 'r' and 't' both appear once. So 'e' must appear before both 'r' and 't'. Therefore "eetr" is also a valid answer.
Input: s = "cccaaa" Output: "aaaccc" Explanation: Both 'c' and 'a' appear three times, so both "cccaaa" and "aaaccc" are valid answers. Note that "cacaca" is incorrect, as the same characters must be together.
Input: s = "Aabb" Output: "bbAa" Explanation: "bbaA" is also a valid answer, but "Aabb" is incorrect. Note that 'A' and 'a' are treated as two different characters.
1 <= s.length <= 5 * 105
s consists of uppercase and lowercase English letters and digits.
I love this problem because it made me think a bit more, I had to think of a cool data structure that would house my data and allow me to access it quickly and comfortably without hassle. So, I used a Map
My first step was to go through the string of characters and populate my dataset with the characters and their counts.
Then I sorted the resulting dataset in descending order because the question specifically required that.
After sorting, I looped through the sorted dataset and grabbed the character and its count. Then I used those variables to populate my resulting string and feedback to the program.
This process would have been explained better with code snippets, forgive me. I'm just following instructions.
Time Complexity: O(nlog(n)) Space Complexity: O(n)
Thanks for reading through, I hope you learned a thing or two. Will see you in the next challenge post.
Please share your thoughts in the comment section, let's talk :-)
Your friend in progress,