Alternate Lower Upper String Sort | C ++ program for unusul string sorting ; Function for alternate sorting of string ; Count occurrences of individual lower case and upper case characters ; Traverse through count arrays and one by one pick characters . Below loop takes O ( n ) time considering the MAX is constant . ; Driver code
#include <bits/stdc++.h> NEW_LINE using namespace std ; #define MAX  26 NEW_LINE void alternateSort ( string & s ) { int n = s . length ( ) ; int lCount [ MAX ] = { 0 } , uCount [ MAX ] = { 0 } ; for ( int i = 0 ; i < n ; i ++ ) { if ( isupper ( s [ i ] ) ) uCount [ s [ i ] - ' A ' ] ++ ; else lCount [ s [ i ] - ' a ' ] ++ ; } int i = 0 , j = 0 , k = 0 ; while ( k < n ) { while ( i < MAX && uCount [ i ] == 0 ) i ++ ; if ( i < MAX ) { s [ k ++ ] = ' A ' + i ; uCount [ i ] -- ; } while ( j < MAX && lCount [ j ] == 0 ) j ++ ; if ( j < MAX ) { s [ k ++ ] = ' a ' + j ; lCount [ j ] -- ; } } } int main ( ) { string str = " bAwutndekWEdkd " ; alternateSort ( str ) ; cout << str << " STRNEWLINE " ; }