fork download
copy 
  1. // C++ program to rearrange characters in a string 
  2. // so that no two adjacent characters are same. 
  3. #include<bits/stdc++.h> 
  4. using namespace std; 
  5.  
  6. const int MAX_CHAR = 26; 
  7.  
  8. struct Key 
  9. { 
  10.     int freq; // store frequency of character 
  11.     char ch; 
  12.  
  13.     // function for priority_queue to store Key 
  14.     // according to freq 
  15.     bool operator<(const Key &k) const
  16.     { 
  17.         return freq < k.freq; 
  18.     } 
  19. }; 
  20.  
  21. // Function to rearrange character of a string 
  22. // so that no char repeat twice 
  23. void rearrangeString(string str) 
  24. { 
  25.     int n = str.length(); 
  26.  
  27.     // Store frequencies of all characters in string 
  28.     int count[MAX_CHAR] = {0}; 
  29.     for (int i = 0 ; i < n ; i++) 
  30.         count[str[i]-'a']++; 
  31.  
  32.     // Insert all characters with their frequencies 
  33.     // into a priority_queue 
  34.     priority_queue< Key > pq; 
  35.     for (char c = 'a' ; c <= 'z' ; c++) 
  36.         if (count[c-'a']) 
  37.             pq.push( Key { count[c-'a'], c} ); 
  38.  
  39.     // 'str' that will store resultant value 
  40.     str = "" ; 
  41.  
  42.     // work as the previous visited element 
  43.     // initial previous element be. ( '#' and 
  44.     // it's frequency '-1' ) 
  45.     Key prev {-1, '#'} ; 
  46.  
  47.     // traverse queue 
  48.     while (!pq.empty()) 
  49.     { 
  50.         // pop top element from queue and add it 
  51.         // to string. 
  52.         Key k = pq.top(); 
  53.         pq.pop(); 
  54.         str = str + k.ch; 
  55.  
  56.         // IF frequency of previous character is less 
  57.         // than zero that means it is useless, we 
  58.         // need not to push it 
  59.         if (prev.freq > 0) 
  60.             pq.push(prev); 
  61.  
  62.         // make current character as the previous 'char' 
  63.         // decrease frequency by 'one' 
  64.         (k.freq)--; 
  65.         prev = k; 
  66.     } 
  67.  
  68.     // If length of the resultant string and original 
  69.     // string is not same then string is not valid 
  70.     if (n != str.length()) 
  71.         cout << " Not valid String " << endl; 
  72.  
  73.     else // valid string 
  74.         cout << str << endl; 
  75. } 
  76.  
  77. // Driver program to test above function 
  78. int main() 
  79. { 
  80.     string str = "bbbaa" ; 
  81.     rearrangeString(str); 
  82.     return 0; 
  83. }
Success #stdin #stdout 0s 4372KB
comments (?)
stdin
copy 
Standard input is empty
stdout
copy 
babab
https://ideone.com/n5q27A
language:
C++ (gcc 8.3)
created:
4 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!