Sort Characters By Frequency

Given a string s, sort the characters in the string based on their frequency in non-increasing order.

Example:

Input:

s = "tree"

Output:

"eert"

Explanation: In the input string, ‘e’ appears twice, ‘r’ appears once, and ‘t’ appears once. The characters are sorted based on their frequency in non-increasing order, which gives us the output “eert”.

Solution in C++:

#include <iostream>
#include <string>
#include <unordered_map>
#include <algorithm>

// Function to sort characters by frequency
std::string frequencySort(std::string s) {
    // Create a hash map to store character frequency
    std::unordered_map<char, int> freqMap;

    // Count the frequency of each character in the string
    for (char c : s) {
        freqMap[c]++;
    }

    // Sort the characters based on their frequency in non-increasing order
    std::sort(s.begin(), s.end(), [&](char a, char b) {
        return freqMap[a] > freqMap[b] || (freqMap[a] == freqMap[b] && a < b);
    });

    return s;
}

int main() {
    std::string s = "tree";
    std::string result = frequencySort(s);
    std::cout << "Sorted characters by frequency: " << result << std::endl;

    return 0;
}

Explanation:

1. The frequencySort function takes a string s as input and returns a string with the characters sorted by frequency.
2. Inside the frequencySort function, we create a freqMap using an unordered map (hash map) to store the frequency count of each character in the input string s.
3. We then use a lambda function as a custom comparator to sort the characters in s. The lambda function sorts the characters based on their frequency in non-increasing order. If two characters have the same frequency, they are sorted in ascending order based on their ASCII values. This ensures stable sorting, meaning characters with the same frequency retain their relative order.

Time Complexity:

The time complexity of this solution is O(n log n), where n is the length of the input string s. This is because the sorting step using std::sort dominates the overall time complexity.

Space Complexity:

The space complexity of this solution is O(n), where n is the length of the input string s. This is because we are using an unordered map to store the frequency count of each character in the string. In the worst case, all unique characters in the string will be added to the map.