W oparciu o twoje rady opracowalem juz kilka programów, jednak żaden z nich nie zadziałał wstarczająco szybko, dla wymogów tego zadania.
Wklejam tutaj to, co wydaje mi się najlepszym z wymyślonych przezemnie sposobów. Nie mam za bardzo pomysłu co jeszcze może być tutaj za wolne. Miałem też zalążek pomysłu z rekurencją, ale narazie stanąłem tam w martwym punkcie.
#include <iostream>
#include <string>
using namespace std;
char kolej[1000000];
int main()
{
int ile_powtorzen;
cin>>ile_powtorzen; //wybieramy iloscpowtorzen i rozpoczyna sie petla ktora wykona wczytywania
for(int i=1; i<=ile_powtorzen; i++)
{
char *ok_kolej;
ok_kolej = new char[1000000]; //za pomoca wskaznika deklarujemy robocza tabele char
cin>>kolej; //wprowadzamy pierwotna kolejke
int ile=0;
while(kolej[ile]!=NULL) ile++; //int ile jest licznikiem w petli okreslajacej dlogosc pierwotnej kolejki
char przod=kolej[ile-1]; //okreslamy robocza zmienna przod
int bufor=0; //bufor jest licznikiem do pracy i zapisu w roboczej tabeli ok_kolej
for(int j=ile-2; j>=0; j--) //petla rozpoczyna od tylu do przodu kolejki
{
if((int)kolej[j]>=(int)przod) //to wyrazenie szuka danej litery, ktora bedzie wieksza od aktualnego przodu
{
ok_kolej[bufor]=przod; //jezeli znajdzie taka litere to wpisuje aktualny przod do ok_kolei
przod=kolej[j]; //a potem znaleziona wieksza litera staje sie przodem
bufor++; //bufor jest powiekszany
}
}
ok_kolej[bufor]=przod; //jezeli porownanie dotarlo do konca ozancza to ze aktualny przod jest najwiekszy i powinien wyladaowac w ok_kolei
ok_kolej[bufor+1]=NULL; //dodajemy na koncu ok_kolei NULL, dla zachowania zasad STRING (nie wiem czy to potrzebne)
for(int j=bufor; j>=0; j--) cout<<ok_kolej[j]; //nalezy odwrocic kolej tak by najwieksze litery znalazly sie na poczatku, a nie na koncu
cout<<endl;
delete [] ok_kolej; //robocza ok_kolej jest usuwana z pamieci przed powtorzeniem petli
}
return 0;
}
]
A < Z < a < z .... a x? x < A < Z < a < z czy A < x < Z < a czy...? 
