101 Logo
onenoughtone

Solution Approach

Solution Overview

There are 3 main approaches to solve this problem:

  1. Hash Map and Sorting - Complex approach
  2. Bucket Sort Approach - Complex approach
  3. Priority Queue (Heap) Approach - Complex approach

Approach 1: Hash Map and Sorting

Let's start by understanding the problem: we need to sort characters in a string based on their frequencies, with more frequent characters appearing first.

Thinking Process: The first step is to count the frequency of each character in the string. We can use a hash map (or dictionary) to store the character counts. Then, we need to sort the characters based on their frequencies in descending order.

After sorting, we can build the result string by appending each character the number of times it appears in the original string.

Intuition: This approach directly follows the problem statement. We count frequencies, sort based on those frequencies, and then construct the result string.

Algorithm:

  1. Create a hash map to store the frequency of each character in the string.
  2. Iterate through the string and count the frequency of each character.
  3. Create a list of characters from the hash map.
  4. Sort the list of characters based on their frequencies in descending order.
  5. Build the result string by appending each character the number of times it appears in the original string.
  6. Return the result string.

Time Complexity:

O(n log n)

Where n is the length of the string. Counting frequencies takes O(n) time, sorting takes O(k log k) time where k is the number of unique characters (which is at most 128 for ASCII), and building the result string takes O(n) time. Since k is bounded by a constant, the overall time complexity is dominated by O(n).

Space Complexity:

O(n)

We use a hash map to store character frequencies, which takes O(k) space where k is the number of unique characters. We also need O(n) space for the result string. Since k is bounded by a constant, the overall space complexity is O(n).

Approach 2: Bucket Sort Approach

We can optimize the previous approach by using bucket sort instead of a general sorting algorithm.

Thinking Process: Since the frequency of a character is at most the length of the string, we can use an array of buckets where each bucket corresponds to a frequency. We place characters with the same frequency in the same bucket.

Then, we iterate through the buckets from highest frequency to lowest and append characters to the result string.

Intuition: Bucket sort is more efficient than general sorting algorithms when the range of values to be sorted is limited, which is the case here.

Algorithm:

  1. Create a hash map to store the frequency of each character in the string.
  2. Iterate through the string and count the frequency of each character.
  3. Create an array of buckets where each bucket corresponds to a frequency.
  4. Place characters with the same frequency in the same bucket.
  5. Iterate through the buckets from highest frequency to lowest.
  6. For each bucket, append each character in the bucket to the result string the number of times equal to its frequency.
  7. Return the result string.

Time Complexity:

O(n)

Where n is the length of the string. Counting frequencies takes O(n) time, creating buckets takes O(n) time, and building the result string takes O(n) time. The overall time complexity is O(n).

Space Complexity:

O(n)

We use a hash map to store character frequencies, which takes O(k) space where k is the number of unique characters. We also need O(n) space for the buckets and the result string. Since k is bounded by a constant, the overall space complexity is O(n).

Approach 3: Priority Queue (Heap) Approach

Another approach is to use a priority queue (heap) to sort characters by their frequencies.

Thinking Process: We first count the frequency of each character in the string using a hash map. Then, we create a max heap (priority queue) where elements are ordered by their frequencies in descending order.

We pop elements from the heap one by one and append each character to the result string the number of times equal to its frequency.

Intuition: A priority queue is a natural choice for this problem because it allows us to efficiently retrieve the character with the highest frequency at each step.

Algorithm:

  1. Create a hash map to store the frequency of each character in the string.
  2. Iterate through the string and count the frequency of each character.
  3. Create a max heap (priority queue) where elements are ordered by their frequencies in descending order.
  4. Add each character and its frequency to the heap.
  5. Pop elements from the heap one by one.
  6. For each element, append the character to the result string the number of times equal to its frequency.
  7. Return the result string.

Time Complexity:

O(n log k)

Where n is the length of the string and k is the number of unique characters. Counting frequencies takes O(n) time, building the heap takes O(k) time, and popping elements from the heap takes O(k log k) time. Building the result string takes O(n) time. Since k is bounded by a constant, the overall time complexity is O(n).

Space Complexity:

O(n)

We use a hash map to store character frequencies, which takes O(k) space where k is the number of unique characters. We also need O(k) space for the heap and O(n) space for the result string. Since k is bounded by a constant, the overall space complexity is O(n).

Pseudocode

solution.pseudo
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
function frequencySort(s):
    // Count frequency of each character
    freq = new HashMap()
    for each character c in s:
        freq[c] = freq[c] + 1 or 1 if c not in freq
    
    // Sort characters by frequency
    chars = list of keys in freq
    sort chars by freq[c] in descending order
    
    // Build result string
    result = ""
    for each character c in chars:
        result += c repeated freq[c] times
    
    return result
PreviousNext
ProblemSolutionCode
101 Logo
onenoughtone