LeetCode Q316: Remove Duplicate Letters (hard)

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"

Solution:
For explanation please refer to here. Basically, we should use greedy algorithm, try to choose the smallest character as front as possible. We use a stack to save current result string. Each time when met a totally new character is met compared to the tail of the string, if smaller than tail and the tail also shows up in the remaining part, then we can remove tail from stack and insert the new character just met. This is done iteratively.

	class Solution {
	public:
	string removeDuplicateLetters(string s) {
	vector<int> dict(256, 0);
	vector<bool> visited(256, false);
	for(auto ch : s) dict[ch]++;
	string result = "0";
	/** the key idea is to keep a monotically increasing sequence **/
	for(auto c : s) {
	dict[c]--;
	/** to filter the previously visited elements **/
	if(visited[c]) continue;
	while(c < result.back() && dict[result.back()]) // if tail is larger and exist in remaining string, then we can remove it
	{
	visited[result.back()] = false;
	result.pop_back();
	}
	result += c;
	visited[c] = true;
	}
	return result.substr(1);
	}
	};

view raw Q316.cpp hosted with ❤ by GitHub

Round 2 solution:

	class Solution {
	public:
	string removeDuplicateLetters(string s) {
	string res;
	if(s.empty())
	return res;
	vector<int> myCount(128, 0);
	for(int i=0; i<s.length(); i++)
	myCount[s[i]]++;
	stack<int> myStack;
	vector<int> used(128, 0);
	for(int i=0; i<s.length(); i++){
	while(!myStack.empty()&&s[i]<myStack.top()&&myCount[myStack.top()]>=1&&used[s[i]]==0){
	used[myStack.top()]=0;
	myStack.pop();
	}
	if(used[s[i]]==0){
	myStack.push(s[i]);
	used[s[i]]=1;
	}
	myCount[s[i]]--;
	}
	while(!myStack.empty()){
	res+=myStack.top();
	myStack.pop();
	}
	reverse(res.begin(), res.end());
	return res;
	}
	};

view raw Q316Rnd2.cpp hosted with ❤ by GitHub