[LeetCode]Rearrange String k Distance Apart

一般来讲越多的字符比越少的字符更加难排，所以每次我们要先排出现次数多的字符，我们用map和priority queue来追踪每个字符出现的数量和当前出现最多的字符。并且用另外一个queue来控制处于冷却区的字符，因为要保证相同的字符至少存在k的距离。这样就可以保证满足k distance的的情况下，每次取出现次数最多的字符。如果在某一步我们发现priority queue空了，说明我们不能做到，返回empty string。这个做法可以给我们正确的结果，但是和其他greedy做法一样，难点在于证明这个算法的正确性，笔者并没有想出来如何证明，也并没有google到如何证明其正确性。
时间复杂度O(n * log 26) = O(n)，代码如下：

	class Solution {
	public:
	string rearrangeString(string s, int k) {
	int len = s.size(), i = 0;
	unordered_map<char, int> map;
	auto comp = [&](const char& lhs, const char& rhs){return map[lhs] < map[rhs];};
	priority_queue<char, vector<char>, decltype(comp)> pq(comp);
	queue<pair<char, int>> cooldown;
	for(auto&& c : s)++map[c];
	for(auto&& p : map)pq.push(p.first);
	string res;
	while(i < len)
	{
	if(pq.empty())return "";
	char c = pq.top();
	pq.pop();
	res += c;
	--map[c];
	if(map[c])//add to cooldown list
	cooldown.push(make_pair(c, i));
	if(cooldown.size() && cooldown.front().second <= i - k + 1)
	{
	auto p = cooldown.front();
	cooldown.pop();
	pq.push(p.first);
	}
	++i;
	}
	return res;
	}
	};

view raw Rearrange String k Distance Apart.cpp hosted with ❤ by GitHub