Depth First Search on the map to build a unique string that depends on the index.

beautiful.cpp

#include <iostream>
#include <string>
#include <vector>
#include <math.h>
#include <map>
#include <algorithm>
#include <vector>
#include <iostream>
#include <set>
#include <list>
#include <queue>
using namespace std;

/*


a 34 42 50 52 80 83
b 45 56 62 79 84 88
c 17 37
d 8 19 28 65 73
e 16 29 44 94 99
f 7 32 54 91
g 5 24 49 71 85
h 2 4 22 92
i 23 40 51 61 64
j 14 25 30 39 41 58 66
k 33 53 63 70 77 87 95
l 1 11 47 57 96 98
m 59 93
n 0 9 10 74 78
o 26 36 43 86
p 12 18 60 82
q 27 46 75
r 6 13 20 48 68 72 81 90 97
s 31 35 55 67 76 89
t 3 15 21 38 69
*/

void print_vv(vector<vector<int>> &x){
    for(auto i = x.begin(); i != x.end(); ++i){
        for( auto j = i->begin(); j != i->end(); ++j){
            cout << *j << " ";
        }
        cout << endl;
    }
}

void print_vl(vector<list<int>> &x){
    for(auto i = x.begin(); i != x.begin()+1; ++i){
        for( auto j = (*i).begin() ; j != (*i).end(); ++j){
            cout << *j << " ";
        }
        cout << endl;
    }
}

bool check( vector<list<int>> &x, int ind ){
    for( auto i = x.begin(); i != x.end(); ++i){
        for(auto j = i->begin(); j != i->end(); ++j){
            if( *j > ind ) return true;
        }
    }
    return false;
}
void build( vector<list<int>> x, map<int, char> ma, string cur, int curr_i, string &largest, int index){
    if( cur.length() > largest.length() )
        largest = cur;
    else if( cur.length() == largest.length() && cur > largest)
        largest = cur;
    if( !check(x, index) )
        return;

    string temp;
    for( auto i = x.begin(); i != x.end(); ++i){
        //cout << index << ": ";
        while( !i->empty() && index > i->front() ){
            //cout << i->front() << " ";
            i->pop_front();
        }
        //cout << endl;
    }

    for( int i = x.size()-1; i >= 0; i-- ){
        if( i == curr_i ) continue;
        if( cur.find(ma[i]) == string::npos ){
            temp = cur + ma[i];
            std::cout << temp << endl;
            build(x,ma,temp,curr_i, largest,x[i].front());
        }
    }

}

void pop( map<char, vector<int>> &m){
    vector< list<int>> mo(m.size(), list<int>());
    map<int, char> ma;
    int j = 0, count =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++;
    }

    string largest, current;
    int curr_i = mo.size()-1;
    //current = new string("");
    for( auto i = mo.rbegin(); i != mo.rend(); ++i){
        current = ma[curr_i];
        build(mo, ma, current, curr_i, largest, i->front());
        curr_i--;
    }
    cout << largest << endl;
}

void crawl( map<char, vector<int>> &m, string current, string &largest, int index, int size){
    if( index >= size ) return;
    string x = "", prev = "";
    int x_i = -1;
    cout << current << endl;
    char last = current[current.length()-1];
    for( auto i = m.rbegin(); i != m.rend(); ++i ){
        if( last == i->first ) continue;
        x_i = -1;
        for( int k = 0; k != i->second.size(); k++){
            if( i->second[k] > index ){
                x_i = i->second[k];
                break;
            }
        }
        if( x_i != -1 && current.find(i->first) == string::npos) {
            x = current + i->first;
            if( (x.length() > largest.length()) || (x.length() == largest.length() && x > largest)){
                largest = x;                
            }

            crawl( m, x, largest, x_i, size);
        }
        else if( x_i == -1 ) 
            return;
    }
}


void ds(string c, string &d){
    string ds = "sfdfd";
    d = c;
    d = ds;
}

int main(){
    string x = "nlhthgrfdnnlprjtecpdrthigjoqdejsfkasoctjijaoebqlrgaiakfsbljmpibkidjsrtkgrdnqsknbarpabgokbsrfhmeklrle", x2;
    string result;
    //crawl(x, 0, result);
    map<char, vector<int>> m;
    string max, current, largest = "";
    //    int index;
    //set<char> d;
    for(int i = 0; i < x.length(); i++){
        m[x[i]].push_back(i);
        //  d.insert(x[i]);
    }
    pop(m);

  
    // use map and branch out, looking for largest string i can build

    //for( auto i = m.rbegin(); i != m.rend(); ++i ){        
    //    current = i->first;
    //    cout << ". ";
    //    crawl(m, current, largest, i->second.front(), x.size());      
    //}

    cout << largest << endl;
    // cout << d.size() << endl;
    cout << endl << "Done." <<endl;
    cin.get();
    cin.get();
    return 0;
}