text: Rearrange characters in a string such that no two adjacent are same | C ++ program to rearrange characters in a string so that no two adjacent characters are same . ; store frequency of character ; function for priority_queue to store Key according to freq ; Function to rearrange character of a string so that no char repeat twice ; Store frequencies of all characters in string ; Insert all characters with their frequencies into a priority_queue ; ' str ' that will store resultant value ; work as the previous visited element initial previous element be . ( ' # ' and it ' s ▁ frequency ▁ ' - 1 ' ) ; traverse queue ; pop top element from queue and add it to string . ; IF frequency of previous character is less than zero that means it is useless , we need not to push it ; make current character as the previous ' char ' decrease frequency by ' one ' ; If length of the resultant string and original string is not same then string is not valid ; valid string ; Driver program to test above function
code: #include <bits/stdc++.h> NEW_LINE using namespace std ; const int MAX_CHAR = 26 ; struct Key { int freq ; char ch ; bool operator< ( const Key & k ) const { return freq < k . freq ; } } ; void rearrangeString ( string str ) { int n = str . length ( ) ; int count [ MAX_CHAR ] = { 0 } ; for ( int i = 0 ; i < n ; i ++ ) count [ str [ i ] - ' a ' ] ++ ; priority_queue < Key > pq ; for ( char c = ' a ' ; c <= ' z ' ; c ++ ) { int val = c - ' a ' ; if ( count [ val ] ) { pq . push ( Key { count [ val ] , c } ) ; } } str = " " ; Key prev { -1 , ' # ' } ; while ( ! pq . empty ( ) ) { Key k = pq . top ( ) ; pq . pop ( ) ; str = str + k . ch ; if ( prev . freq > 0 ) pq . push ( prev ) ; ( k . freq ) -- ; prev = k ; } if ( n != str . length ( ) ) cout << " ▁ Not ▁ valid ▁ String ▁ " << endl ; else cout << str << endl ; } int main ( ) { string str = " bbbaa " ; rearrangeString ( str ) ; return 0 ; }