Day 5 - Sort Characters By Frequency - Leetcode Problem Solved

Day 5 - Sort Characters By Frequency - Leetcode Problem Solved

#I4G10DaysOfCodeChallenge - Day 5

ยท

2 min read

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.

Sort Characters By Frequency

#I4G10DaysOfCodeChallenge


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.

Example 1:

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.

Example 2:

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.

Example 3:

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.

Constraints:

  • 1 <= s.length <= 5 * 105

  • s consists of uppercase and lowercase English letters and digits.

Thought Process

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)

Closing

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,

CodeProphet.

Did you find this article valuable?

Support Emmanuel Obi by becoming a sponsor. Any amount is appreciated!

ย