Heap-assisted greedy (Greedy Sub-pattern)

// Repeatedly merge the two smallest (Huffman cost, connecting ropes).
long long mergeTwoSmallest(const vector<int>& w) {
    priority_queue<long long, vector<long long>, greater<long long>> pq(w.begin(), w.end());
    long long cost = 0;
    while (pq.size() > 1) {
        long long a = pq.top(); pq.pop();
        long long b = pq.top(); pq.pop();
        cost += a + b;
        pq.push(a + b);                                      // the merged node may be the next smallest
    }
    return cost;
}

// Most frequent first, never the same as the last one (no two equal neighbours).
string noTwoAdjacent(const string& s) {
    int cnt[26] = {};
    for (char ch : s) cnt[ch - 'a']++;
    priority_queue<pair<int,char>> pq;                       // {count, letter}, biggest count on top
    for (int c = 0; c < 26; c++) if (cnt[c]) pq.push({cnt[c], char('a' + c)});
    string out;
    while (pq.size() >= 2) {
        auto [c1, x] = pq.top(); pq.pop();
        auto [c2, y] = pq.top(); pq.pop();
        out += x; out += y;                                  // two different letters per round
        if (--c1) pq.push({c1, x});
        if (--c2) pq.push({c2, y});
    }
    if (!pq.empty()) {
        if (pq.top().first > 1) return "";                   // one letter left over more than once
        out += pq.top().second;
    }
    return out;
}