algoadvance

Leetcode 451. Sort Characters By Frequency

Problem Statement

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

Example

Input: "tree"
Output: "eert"

Input: "cccaaa"
Output: "cccaaa" or "aaaccc"

Input: "Aabb"
Output: "bbAa" or "bbaA"

Clarifying Questions

1. Can the input string contain any character?
   • Yes, the input string can contain any printable characters.
2. What should be done in the case of characters that have the same frequency?
   • If characters have the same frequency, the order doesn’t matter for these characters.
3. Can the input string be empty?
   • Yes, the input string can be empty. In that case, the output should also be an empty string.
4. What is the maximum length of the input string?
   • Assume the maximum length of the input string will fit comfortably within typical memory constraints for a C++ program.

Strategy

1. Frequency Counting: Use a hash map to count the frequency of each character.
2. Bucket Sort: Create an array of vectors where the index represents the frequency, and each vector at an index stores characters having that frequency.
3. Output Construction: Traverse the array from the highest frequency to the lowest and construct the output string.

This ensures that characters are appended in the order of their frequency.

Time Complexity

• Counting characters takes (O(n)) time where (n) is the length of the string.
• Bucket sorting and constructing the output string both take (O(n)) time since we process each character only a limited number of times.
• Therefore, the overall time complexity is (O(n)).

Code

Here is the C++ implementation of the strategy:

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

using namespace std;

string frequencySort(string s) {
    // Frequency counting
    unordered_map<char, int> freq;
    for (char c : s) {
        freq[c]++;
    }

    // Bucket sort: index represents frequency
    vector<vector<char>> buckets(s.size() + 1);
    for (const auto& pair : freq) {
        buckets[pair.second].push_back(pair.first);
    }

    // Constructing the result
    string result;
    for (int i = s.size(); i > 0; --i) {
        for (char c : buckets[i]) {
            result.append(i, c);
        }
    }

    return result;
}

// For testing
int main() {
    string input = "tree";
    cout << frequencySort(input) << endl;  // Output should be "eert" or similar
    return 0;
}

Explanation:

1. Counting Frequencies:
   • We use an unordered map to count the frequency of each character in the string.
2. Bucket Sort:
   • We create a vector of vectors where the index corresponds to the frequency of characters.
   • Characters are placed into the appropriate buckets according to their frequencies.
3. Building the Result:
   • We iterate from the highest possible frequency to the lowest and append characters to the result string based on their frequency.

This method ensures that characters are sorted by their frequency in descending order efficiently.

Cut your prep time in half and DOMINATE your interview with AlgoAdvance AI

• 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?