#316 Remove Duplicate Letters

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

Example 1:

Input: s = "bcabc"
Output: "abc"

Example 2:

Input: s = "cbacdcbc"
Output: "acdb"

Solution :

string removeDuplicateLetters(string s) {
map umap;
map umap1;
string result = “”;
stack st;
for(int i=0; i<s.length(); i++)
umap[s[i]]=i;

    st.push(s[0]);
    umap1[s[0]] = true;

    for(int i=1; i<s.length(); i++) {
        if (umap1[s[i]] == false) {

            while(!st.empty() && st.top() > s[i] && umap[st.top()] > i) {
                umap1[st.top()] = false;
                st.pop();
            }

            st.push(s[i]);
            umap1[s[i]] = true;
        }
    }

    while(!st.empty()) {
        result += st.top();
        st.pop();
    }
    reverse(result.begin(), result.end());
    return result;
}

// function that remove duplicate letters
#include <bits/stdc++.h>
using namespace std;

string removeDuplicateLetters(string s) {
	map<char, int> umap;
	string result;
	for(int i=0; i<s.length(); i++)
		umap[s[i]]++;
	
	for(auto i:umap)
		result.push_back(i.first);
	return result;
}

string removeDuplicateLettersWithLexicographicalOrder(string s) {
	map<char, int> umap;
	map<char, bool> umap1;
	string result = "";
	stack<char> st;
	for(int i=0; i<s.length(); i++)
		umap[s[i]]=i;

	st.push(s[0]);
        umap1[s[0]] = true;
    
    for(int i=1; i<s.length(); i++) {
        if (umap1[s[i]] == false) {

            while(!st.empty() && st.top() > s[i] && umap[st.top()] > i) {
                umap1[st.top()] = false;
                st.pop();
            }

            st.push(s[i]);
            umap1[s[i]] = true;
        }
    }

    while(!st.empty()) {
        result += st.top();
        st.pop();
    }
    reverse(result.begin(), result.end());
    return result;
}

int main()
{
	string s = "cbacdcbc";
	//cout << removeDuplicateLetters(s);
	cout << removeDuplicateLettersWithLexicographicalOrder(s);
	return 0;
}