Beautiful String. More beautiful if bigger than the other. More beautiful if string is lexicographically bigger than the other, when they're equal length. This code gets the most beautiful unique string from a given string.

Beautiful.cpp

#include <iostream>
#include <string>
#include <vector>
#include <map>
#include <set>
#include <list>
using namespace std;

bool valid( map<char, vector<int>> m, string me){
    // this one checks if a string is valid
    // valid just means if the letters are in order
    // according to the map given.
    int k = -1;
    int prev = -1;
    for( int i = 0; i < me.length(); i++){
        for( int j = 0; j < m[me[i]].size(); j++){
            k = m[me[i]][j];
            if( k > prev ){
                prev = k;
                break;
            }
        }
        if( prev > k ) 
            return false;
    }

    return true;
}

void build( map<char,vector<int>> &m, vector<list<int>> x, map<int, char> ma, string cur, string &largest, int index, bool &deeper){
    // update largest
    if( cur.length() > largest.length() )
        largest = cur;
    else if( cur.length() == largest.length() && cur > largest)
        largest = cur;

    // pop out indices that are before the current
    // index, they can't be used for where we are 
    string temp;
    int ind = 0;
    for( auto i = x.begin(); i != x.end(); ++i){
        while( !i->empty() && index > i->front() ){
            i->pop_front();
        }
        if ( i->empty() && cur.find(ma[ind]) == string::npos)
            return;
        ind++;
    }

    // now appened any viable letters to current string
    // if we found a solution with a maximum length
    // we have to stop.
    // this is because we got there greedily and therefore
    // we have chosen the max everytime
    for( auto i = ma.rbegin(); i != ma.rend(); ++i){
        if( cur.find(i->second) == string::npos ){
            temp = cur + i->second;
            if( valid(m, temp) ){
                if( temp.length() == ma.size() ){
                    largest = temp;
                    deeper = false;
                    return;
                }
                if(deeper)
                    build(m, x,ma,temp, largest,x[i->first].front(), deeper);
            }
        }
    }

}

void pop( map<char, vector<int>> &m){
   
    // build a vector of lists, where each vector
    // represents a letter and the list is the indices
    // where they occur
    // 'ma' is just a map that connects vector index on 'mo'
    // to a letter
    vector< list<int>> mo(m.size(), list<int>());
    map<int, char> ma;
    int j = 0;
    for( auto i = m.begin(); i != m.end(); ++i){
        for( auto k = i->second.begin(); k != i->second.end(); ++k){
            mo[j].push_back(*k);
        }
        ma[j] = i->first;
        j++;
    }

    // start building the string
    // start with the biggest letter first
    // (at the end)
    string largest, current;
    int curr_i = mo.size()-1;
    bool deeper = true;
    for( auto i = mo.rbegin(); i != mo.rend(); ++i){
        current = ma[curr_i];
        if( deeper ) 
            build(m, mo, ma, current, largest, i->front(), deeper);        
    }
    cout << largest << endl;
}

int main(){
    string x = "nlhthgrfdnnlprjtecpdrthigjoqdejsfkasoctjijaoebqlrgaiakfsbljmpibkidjsrtkgrdnqsknbarpabgokbsrfhmeklrle", x2;
    string result;
    map<char, vector<int>> m;
    for(int i = 0; i < x.length(); i++){
        m[x[i]].push_back(i);
    }

    pop(m);

    cout << endl << "Done." <<endl;
    cin.get();
    cin.get();
    return 0;
}

In: nlhthgrfdnnlprjtecpdrthigjoqdejsfkasoctjijaoebqlrgaiakfsbljmpibkidjsrtkgrdnqsknbarpabgokbsrfhmeklrle
Out: tsocrpkijgdqnbafhmle

In: baba
Out: ba