Frequency Compression

Given a list of character, frequency pairs (sorted by frequency), compress this list into a new list that groups all common frequencies together, and in the process concatenates the cooresponding character together.

For example

Input: {a, 4}, {b, 3}, {c, 3}, {d, 3}, {e, 10}, {f, 10}, {g, 10}, {z, 10}
Output: {a, 4}, {b, 3}, {cd, 3}, {efgz, 10}
vector<pair<string, int>> group_freq_pairs(const vector<pair<char, int>> &char_freq_s) {

    if (char_freq_s.size() == 1) {
        return { { string(1, char_freq_s[0].first), char_freq_s[0].second } };
    }
    vector<pair<string, int>> freq_pairs;
    string s_builder;
    bool last_done = false;
    int end = char_freq_s.size();

    for (int i = 1; i < end; i++) {
        if (char_freq_s[i - 1].second == char_freq_s[i].second) {
            int freq = char_freq_s[i - 1].second;
            s_builder.push_back(char_freq_s[i - 1].first);
            while (i < char_freq_s.size() && char_freq_s[i - 1].second == char_freq_s[i].second) {
                s_builder.push_back(char_freq_s[i++].first);
            }
            freq_pairs.push_back({ s_builder, freq });
            s_builder.clear();
            --i;
            last_done = true;
        }
        else if (!last_done) {
            freq_pairs.push_back({ string(1, char_freq_s[i - 1].first),
                char_freq_s[i - 1].second });
            last_done = false;
        }
        else {
            freq_pairs.push_back({ string(1, char_freq_s[i].first),
                char_freq_s[i].second });
            last_done = true;
        }
    }

    if (!last_done) {
        freq_pairs.push_back({ string(1, char_freq_s[end - 1].first),
            char_freq_s[end - 1].second });
    }

    return freq_pairs;
}

Last updated