[LeetCode]Remove Duplicate Letters

这道题要求字典序最小的结果。但是在我们尽量求小的同时，我们还需要注意在扫过某个字符c最后出现的位置之前要保证一定取过c。为了满足这一点，我们的策略是，首先求出所有字符最后出现的位置lastPos，比如对于字符串caccabad，我们有lastPos = [c->3, b->5, a->6, d->7]。我们每次取lastPos中取最小的value pos，我们有currLeft初始值为0，每次在[currLeft, pos]的区间去最小的char加入结果集。之后更新currLeft = pos + 1，并且remove lastPos中对于的entry，并且重复上述的步骤，注意已经取过的字符我们要跳过。这样我们可以保证满足在扫过某个字符c最后出现的位置之前取过c并且使得字典序最小，因为我们每次都是取满足条件的最小值。同样对于例子s = caccabad：

1. 首先pos = 3，currLeft = 0，[0, 3]中我们取到最小值s[1] = a。currLeft = 2，lastPos remove a
2. pos仍然为3，currLeft = 2，[2, 3]中最小值s[2] = c。currLeft = 3，lastPos remove c，发现我们现在应该更新pos，因为c我们已经取过了，就不需要在意c最后出现的位置了，我们应该关注下一个。pos = 5。
3. pos = 5， currLeft = 3，[3, 5]中最小值并且之前没有出现过的只有s[5] = b。currLeft = 6，lastPos remove b，同理更新pos = 7，因为此时lastPos只剩下d了。
4. pos = 7，currLeft = 6，[6, 7]中最小值并且之前没有出现过的只有s[7] = d。
5. 找到答案acbd，跳出循环。

循环的过程中可能会回溯，1步骤中我们扫了[0, 3]，第二步中我们又重复扫了[2,3]，但是鉴于总共有26个字符，所以时间复杂度为O(26 * n) = O(n)，空间复杂度O(n)，代码如下：

循环：

	class Solution {
	public:
	string removeDuplicateLetters(string s) {
	int len = s.size(), start = 0;
	string res = "";
	unordered_map<char, int> lastPos;
	vector<int> sortedLastPos;
	for(int i = 0; i < len; ++i)lastPos[s[i]] = i;
	int resSize = lastPos.size(), end = getMinLastPos(lastPos);
	while(res.size() < resSize)
	{
	int minPos = start;
	char minChar = 'z' + 1;
	for(int i = start; i <= end; ++i)
	{
	if(lastPos.find(s[i]) != lastPos.end() && s[i] < minChar)
	{
	minPos = i;
	minChar = s[i];
	}
	}
	start = minPos + 1;
	res += minChar;
	lastPos.erase(minChar);
	if(minChar == s[end])end = getMinLastPos(lastPos);
	}
	return res;
	}
	private:
	int getMinLastPos(unordered_map<char, int>& map)
	{
	int res = INT_MAX;
	for(auto&& p : map)res = min(res, p.second);
	return res;
	}
	};

view raw Remove Duplicate Letters_iter.cpp hosted with ❤ by GitHub

递归：

	class Solution {
	public:
	string removeDuplicateLetters(string s) {
	int len = s.size(), pos = 0;
	if(!len)return "";
	char minChar = 'z' + 1;
	unordered_map<char, int> map;
	for(auto&& c : s)++map[c];
	for(int i = 0; i < len; ++i)
	{
	char c = s[i];
	if(c < minChar)
	{
	minChar = c;
	pos = i;
	}
	if(!(--map[c]))break;
	}
	string next = s.substr(pos + 1);
	return minChar + removeDuplicateLetters(removeChar(next, minChar));
	}
	private:
	string removeChar(string s, char del)
	{
	string res = "";
	for(auto&& c : s)
	{
	if(c != del)res += c;
	}
	return res;
	}
	};

view raw Remove Duplicate Letters_recursive.cpp hosted with ❤ by GitHub