Sort Characters By Frequency

To solve the problem of sorting the characters in the given string s based on their frequency, we can follow these steps:

1. Count Frequencies: Use a dictionary to count the frequency of each character in the string.
2. Sort Characters by Frequency: Sort the characters based on their frequency in descending order.
3. Build Result: Iterate through the sorted characters and build the result string by repeating each character according to its frequency.

Here’s the code that puts all the steps together:

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14

class Solution:
    def frequencySort(self, s: str) -> str:
        from collections import Counter

        # Step 1: Count the frequencies
        freq_map = Counter(s)

        # Step 2: Sort the characters by frequency
        sorted_chars = sorted(freq_map.keys(), key=lambda char: freq_map[char], reverse=True)

        # Step 3: Build the result string
        result = ''.join([char * freq_map[char] for char in sorted_chars])

        return result

Example Explanation:

• For s = "tree", the output can be "eert" as ’e’ appears twice, and ‘r’ and ’t’ both appear once.
• For s = "cccaaa", the output can be "aaaccc" as both ‘c’ and ‘a’ appear three times.

The time complexity of this solution is (O(n \log n)), where (n) is the length of the string, since we are sorting the characters based on their frequency. The space complexity is (O(n)) as we are using additional data structures to store the frequency counts.

Define the Terms

Define the Interface

Analyze the Input and Output

Identify the Invariants

Identify the constraints

Search the Problem Space

Classify the Problem

Analyze the Examples

Solve the Problem by Hand

Describe the Pattern

Distill the Observations to Create Insights

Brute Force Approach

[2, 0, 4, 1] 0, 1. 2. 3

Analyze Time and Space Complexity

Outline the Solution

• Frequency array to keep track of the frequency of letter in the given input, keep track of the most frequent character location
  • Size must be 58 (capital letters are allowed)
• output as array
• Get the highest frequency value, convert the index value to character
• Append to the output
• Decrement the counter
• Repeat until we reach 0
• We can construct the string sequentially
• Return the output array converted to a string

Key Takeaways

• Blindly memorizing coding patterns
• You try to force yourself coding pattern that is not making the code concise.

t => 1 r => 1 e => 2

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18

# @param {String} s
# @return {String}
def frequency_sort(s)
    frequency = Hash.new(0)

    s.chars.each do |c|
       frequency[c] += 1 
    end

    sorted = frequency.sort_by{|k, v| -v}

    output = []
    sorted.each do |k, v|
       output << (k * v) 
    end

    output.join
end