GCJ 2016 R1A pA. The Last Word ( Greedy )

Dashboard - Round 1A 2016 - Google Code Jam
It is very intuitive to come up with the greedy strategy where, alphabetically less characters go to the back, otherwise to the front.

#include <bits/stdc++.h>
using namespace std;

int main(){
    int T; scanf("%d", &T);
    for( int kase = 1; kase <= T; ++kase ){
        string s; cin >> s;
        deque< char > ans;
        for( int i = 0; i < s.size(); ++i ){
            if( ans.empty() )
                ans.push_back( s[ i ] );
            else{
                if( s[ i ] >= ans.front() )
                    ans.push_front( s[ i ] );
                else
                    ans.push_back( s[ i ] );
            }
        }
        printf("Case #%d: ", kase);
        for( int i = 0; i < ans.size(); ++i )
            printf("%c", ans[ i ]);
        puts("");
    }
    return 0;
}