fork(1) download 
  1. #include <iostream>
  2. #include <string>
  3. #include <vector>
  4. #include <map>
  5. #include <algorithm>
  6.  
  7. bool cmpBySecond(const std::pair<char, int>& a, const std::pair<char, int>& b) {
  8.     if (a.second == b.second) return a.first < b.first;
  9.     return a.second < b.second;
  10. }
  11.  
  12. std::string reorder(const std::string& input) {
  13.     std::map<char, int> cnt;
  14.     for (auto& c: input) cnt[c]++;
  15.     auto items = std::vector<std::pair<char, int>>(cnt.begin(), cnt.end());
  16.     std::sort(items.begin(), items.end(), cmpBySecond);
  17.     std::reverse(items.begin(), items.end());
  18.     // now we have chars with occurencies counts in descending order
  19.     std::string result(input);
  20.     int pos = 0;
  21.     for (auto& it: items) {
  22.         char c = it.first;
  23.         int times = it.second;
  24.         for (int i = 0; i < times; ++i) {
  25.             result[pos] = c;
  26.             pos += 2;
  27.             if (pos >= result.size()) pos = 1;
  28.         }
  29.     }
  30.     return result;
  31. }
  32.  
  33. int main()
  34. {
  35.     std::cout << reorder("aaabb") << std::endl;
  36.     std::cout << reorder("abcde") << std::endl;
  37.     std::cout << reorder("aaabbb") << std::endl;
  38.     std::cout << reorder("aabbc") << std::endl;
  39.     std::cout << reorder("qqqq") << std::endl;
  40. }
  41.  
Success #stdin #stdout 0s 3460KB
comments (?)
stdin 
Standard input is empty
stdout 
ababa
ebdac
bababa
babca
qqqq
https://ideone.com/KnQLIu
language:
C++14 (gcc 8.3)
created:
8 years ago
visibility:
public

Share or Embed source code

Discover > Sphere Engine API

The brand new service which powers Ideone!

Discover > IDE Widget

Widget for compiling and running the source code in a web browser!