316 Remove Duplicate Letters

Given a string which contains only lowercase letters, remove duplicate letters so that every letter appear once and only once. You must make sure your result is the smallest in lexicographical order among all possible results.

Example:
Given "bcabc"
Return "abc"

Given "cbacdcbc"
Return "acdb"

// attempt: 1 -> does not return in smallest lexical-graphical order

#include <iostream>
#include <string>
#include <vector>
#include <algorithm>
#include <map>

using namespace std;

void print1d(vector<int> &nums) { for (auto i : nums) cout << i << ' '; cout << endl; }

void printMap(map<char, int> &myMap) {
    for (auto i : myMap) {
        cout << i.first << " => " << i.second << endl;
    }
}

map<char, int> mapAlpha() {
    map<char, int> alpha;
    for (int i = 0; i < 26; i++) {
        alpha.insert({ static_cast<char>('a' + i), 0 });
    }

    return alpha;
}



string removeDuplicateLetters(string s) {
    map<char, int> alphaCount = mapAlpha();
    //printMap(alphaCount);

    for (int i = 0; i < s.size(); ++i) {
        // duplicate exists
        if (alphaCount.find(s.at(i))->second != 0) {
            s.erase(s.begin() + i);
            i--;
        }
        // unique letter
        else {
            alphaCount.find(s.at(i))->second = 1;
        }
    }
    return s;
}

int main()
{
    string s = "aaacomn";
    string result = removeDuplicateLetters(s);
    cout << result << endl;
}

// attempt2:

Brainstorming:

• For every duplicate, measure its displacement distance to every other non-duplicate element. Then add this elements together. So for every duplicate there will be a number associated with it. Finally, all duplicate positions will be erased from the string, except for the position with the minimum distance.

• Really slow, and I am sure there is a better solution - but it's my current intuition.

Retrospect:

• I will likely rewriting this entire program again from scratch. There are too many redudancies, and very difficult to read implementation. Functions are not reproducable, and I am pretty sure there is an entirely different, but better algorithm that is both simplier and more efficient. This was good practice, I suppose.

#include <iostream>
#include <string>
#include <vector>
#include <algorithm>
#include <math.h>
#include <map>

using namespace std;

void print1d(vector<int> &nums) { for (auto i : nums) cout << i << ' '; cout << endl; }

void printMap(map<char, int> &myMap) {
    for (auto i : myMap) {
        cout << i.first << " => " << i.second << endl;
    }
}

void print2d(vector<vector<int>> &nums)
{
    for (int i = 0; i < nums.size(); i++) {
        for (int j = 0; j < nums.at(i).size(); j++) {
            cout << nums.at(i).at(j) << ' ';
        }
        cout << endl;
    }
}

void printVectorMap(map<char, vector<int>> &myMap) {
    for (auto i : myMap) {
        cout << i.first << " => {";
        for (int j = 0; j < i.second.size(); j++) {
            cout << i.second.at(j) << ",";
        }
        cout << "}" << endl;
    }
}

map<char, vector<int>> mapAlpha() {
    string alphabet = "abcdefghijklmnopqrstuvwxyz";
    map<char, vector<int>> alpha;
    vector<int> emptyVector;
    for (auto i : alphabet) {
        alpha.insert({ i, emptyVector });
    }
    return alpha;
}

vector<int> findMinIndexPerUniqueCharacter(vector<vector<int>> *nums, map<char, vector<int>> &counts) {
    vector<int> removeTheseIndexPositions;

    int min_index;
    // remove min index location from map
    // print2d((*nums));
    for (int i = 0; i < (*nums).size(); i++) {
        // find min index per character
        if ((*nums).at(i).size() < 1) removeTheseIndexPositions.push_back(-1); // -1 to designate no duplicates
        else {
            min_index = min_element((*nums).at(i).begin(), (*nums).at(i).end()) - (*nums).at(i).begin();
            removeTheseIndexPositions.push_back(min_index);
        }
    }

    int counter = 0;
    // iterate through map, to give us the final duplicates

    //print1d(removeTheseIndexPositions);

    for (std::map<char, vector<int>>::iterator it = counts.begin(); it != counts.end(); ++it) {
        if (removeTheseIndexPositions.at(counter) == -1) {
            counter++;
            continue;
        }
        else {
            it->second.erase(it->second.begin() + removeTheseIndexPositions.at(counter));
            //printVectorMap(counts);
            counter++;
        }
    }

    removeTheseIndexPositions.clear();
    for (auto i : counts) {
        for (int j = 0; j < i.second.size() && i.second.size() > 1; j++) {
            removeTheseIndexPositions.push_back(i.second.at(j));
        }
    }
    print1d(removeTheseIndexPositions);

    return removeTheseIndexPositions;

}

vector<int> duplicatePositions(map<char, vector<int>> &counts, string s) {
    vector<char> duplicatesChars;
    vector<int> duplicatesPos;
    vector<int> nonDuplicatePos;

    // find the duplicated characters
    for (auto i : counts) {
        if (i.second.size() > 1) {
            duplicatesChars.push_back(i.first);
        }
    }

    // link duplicated characters to the original string
    for (int i = 0; i < s.size(); i++) {
        for (int j = 0; j < duplicatesChars.size(); j++) {
            if (s.at(i) == duplicatesChars.at(j)) {
                duplicatesPos.push_back(i);
            }
            else nonDuplicatePos.push_back(i);
        }
    }

    // next we find the duplicate distance

    // every character has with it an associated distance
    // I will use an vector to fold these distances in respective order of the string

    int distanceSum = 0;
    // subset of distances per unique character
    vector<int> uniqueCharDistances;
    vector<vector<int>> distances;

    for (auto i : counts) {
        // > 1 to ignore it if character only appears once
        for (int k = 0; k < i.second.size() && i.second.size() > 1; k++) {
            for (int j = 0; j < nonDuplicatePos.size(); j++) {
                distanceSum += abs(i.second.at(k) - nonDuplicatePos.at(j));
            }
            // gone through the entire vector for duplicate character
            uniqueCharDistances.push_back(distanceSum);
            distanceSum = 0;
        }
        // look at next unique character in the map
        distances.push_back(uniqueCharDistances);
        uniqueCharDistances.clear();
    }

    // I now have to choose the minimum per UNIQUE duplicate element,
    // but this minimum has to be mapped directly with its index location
    //printVectorMap(counts);
    //print2d(distances);
    return findMinIndexPerUniqueCharacter(&distances, counts);

}

vector<int> findDuplicates(string s) {
    map<char, vector<int>> alphaCount = mapAlpha();

    for (int i = 0; i < s.size(); i++) {
        //count all positions for each char
        alphaCount.find(s.at(i))->second.push_back(i);
    }

    return duplicatePositions(alphaCount, s);
}


string removeDuplicateLetters(string s) {
    vector<int> charsToRemove = findDuplicates(s);
    sort(charsToRemove.begin(), charsToRemove.end());
    for (int i = charsToRemove.size() - 1; i >= 0; i--) {
        s.erase(s.begin() + charsToRemove.at(i));
    }

    return s;
}

int main()
{
    string s = "ddddssssaaaaok";
    string result = removeDuplicateLetters(s);
    cout << result << endl;
}

// attempt3: