algoadvance

Given a string s, sort it in decreasing order based on the frequency of characters, and return the sorted string.

Example:

1. Input: s = "tree" Output: "eert"

2. Input: s = "cccaaa" Output: "aaaccc"

3. Input: s = "Aabb" Output: "bbAa"

Constraints:

• 1 <= s.length <= 5 * 10^5
• s consists of uppercase and lowercase English letters and digits.

Clarifying Questions

1. Does the casing (uppercase/lowercase) matter?
   • Yes, case matters, meaning ‘A’ and ‘a’ are considered different characters.
2. If multiple characters have the same frequency, can their order be arbitrary in the output?
   • Yes, their order can be arbitrary in the output.

Strategy

1. Character Frequency Calculation: Use a Counter from the collections module to count the frequency of each character in the string.
2. Sorting: Sort the characters based on their frequency in descending order.
3. Reconstruct the String: Reconstruct the string by repeating each character as per its frequency and concatenate them to form the result.

Detailed Steps:

1. Import the Counter from collections.
2. Count the frequency of each character in the string s.
3. Create a list of characters sorted by their frequency in descending order.
4. Build the result string by multiplying characters by their frequency and joining them together.

Code

from collections import Counter

def frequencySort(s: str) -> str:
    # Step 1: Count the frequency of each character
    frequency = Counter(s)
    
    # Step 2: Sort the characters based on their frequency in descending order
    sorted_chars = sorted(frequency, key=lambda x: (-frequency[x], x))
    
    # Step 3: Reconstruct the string
    result = ''.join([char * frequency[char] for char in sorted_chars])
    
    return result

# Example usage:
print(frequencySort("tree"))    # Output: "eert"
print(frequencySort("cccaaa"))  # Output: "aaaccc"
print(frequencySort("Aabb"))    # Output: "bbAa"

Time Complexity

• Counting Frequencies: O(n) where n is the length of the string.
• Sorting: O(m log m) where m is the number of unique characters (at most this is 62, for 26 lowercase + 26 uppercase + 10 digits, thus this can be considered O(1)).
• Reconstructing String: O(n) since we concatenate n characters.

Overall, the time complexity is O(n log m + n) which simplifies to O(n log m) and can be approximated to O(n) given that m is a constant (bounded by 62).

Try our interview co-pilot at AlgoAdvance.com

• Got blindsided by a question you didn’t expect?

• Spend too much time studying?

• Or simply don’t have the time to go over all 3000 questions?