451. Sort Characters By Frequency - Detailed Explanation

Problem Statement

Given a string s, the task is to sort the characters in s in decreasing order based on the frequency of each character. The characters that occur more frequently should come first in the sorted string. In case two characters have the same frequency, their relative order does not matter. The output should be the newly formed string after sorting.

Example Inputs, Outputs, and Explanations

Example 1

• Input: s = "tree"
• Output: "eert"
• Explanation:
  The character 'e' appears twice, while 't' and 'r' appear once each. Therefore, 'e' comes first. One valid sorted result is "eert". Other variations such as "eetr" are also acceptable.

Example 2

• Input: s = "cccaaa"
• Output: "cccaaa" or "aaaccc"
• Explanation:
  Both 'c' and 'a' appear three times. The sorted order groups the same characters together, but the order of these groups does not matter.

Example 3

• Input: s = "Aabb"
• Output: "bbAa"
• Explanation:
  Here, 'b' appears twice while 'A' and 'a' appear once each. The output shows 'b' first, followed by the other characters. Note that uppercase and lowercase characters are treated as distinct.

Hints

• Counting Frequencies:
  Use a hash map (or dictionary) to count the frequency of each character in the string.

• Sorting by Frequency:
  After obtaining the frequency count, sort the characters in descending order based on these counts.

• Building the Result:
  Once sorted, construct the final string by repeating each character as many times as it occurs in the original string.

Approach: Frequency Counting and Sorting

Explanation

1. Frequency Count:
   Traverse the string and count how many times each character appears using a hash map or dictionary.

2. Sort Characters by Frequency:
   With the frequency data, sort the unique characters in descending order according to their counts. You can use built-in sorting functions with a custom key that sorts based on frequency.

3. Construct the Result String:
   Iterate over the sorted characters and append each character repeated by its frequency to build the final output string.

Step-by-Step Walkthrough

Consider the input string s = "tree":

• Step 1: Count frequencies.

  • 't' → 1
  • 'r' → 1
  • 'e' → 2

• Step 2: Sort the characters by frequency in descending order.

  • The sorted order based on frequency is: 'e', followed by 't' and 'r' (the order of 't' and 'r' does not matter as they have equal frequency).

• Step 3: Construct the output string.

  • For 'e', append "ee".
  • For 't', append "t".
  • For 'r', append "r".
  • The resulting string is "eetr" (or "eert" if the order of 't' and 'r' is swapped).

Complexity Analysis

• Time Complexity:

  • Counting the characters takes O(n), where n is the length of the string.

  • Sorting the unique characters takes O(k log k), where k is the number of unique characters. Since k is bounded by the character set (for example, 26 for lowercase letters or a constant in the case of ASCII), this step is effectively O(1) compared to O(n) in many practical scenarios.

  • Building the result string takes O(n).

  • Overall, the solution runs in O(n) time.

• Space Complexity:

  • O(n) space is required to build the output string and O(k) space for the frequency counter. Thus, the total space complexity is O(n).

Python Code