Day 5 - Sort Characters By Frequency - Leetcode Problem Solved

Day 5 - Sort Characters By Frequency - Leetcode Problem Solved

#I4G10DaysOfCodeChallenge - Day 5

The Task

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.

Thought Process

Input: A string of characters.
Expected Output: A formatted string with characters arranged in decreasing order of their occurrence of the inputted string. There should be the same amount of characters as the inputted string also.

With this in mind, this was how I went about solving the task:

  1. Split the string into a set of characters (a set contains just one occurrence of each character of the string).
  2. Iterate through the set. For each character in the set, check the number of times it occurred in the inputted string.
  3. Create a string of the character with length n, n being its count gotten above.
  4. Append this string to an array

    At the end of this iteration, we'll get an array of strings. Each string is a character of the input repeated by its count in the input.

  5. We sort this string by the length of the elements inside it, this puts the longest strings at the beginning of the array and the shortest ones at the end.
  6. We join all the elements of the array together into a final string that will be the return value.

Notes: By creating a set instead of iterating through the string directly, we reduce the number of unnecessary iterations. This helps a lot in reducing the runtime of the solution.