leetcode 767. 重构字符串

给定一个字符串S，检查是否能重新排布其中的字母，使得两相邻的字符不同。

若可行，输出任意可行的结果。若不可行，返回空字符串。

示例 1:

输入: S = "aab"
输出: "aba"
示例 2:

输入: S = "aaab"
输出: ""

struct Node
{
	Node() {}
	Node(char c_, int cnt)
	{
		c = c_;
		count = cnt;
	}

	char c;
	int count;

	friend bool operator < (const Node& other, const Node& other2);
};

bool operator < (const Node& other, const Node& other2)
{
	return other.count < other2.count;
}

class Solution {
public:

	string reorganizeString(string S) {

		priority_queue<Node> que;

		map<char, int> mp;
		for (char c : S)
		{
			mp[c]++;
		}

		for (auto v : mp)
		{
			que.push(Node(v.first, v.second));
		}
		
		string res;
		while (que.size() >= 2)
		{
			Node n1 = que.top();
			que.pop();
			Node n2 = que.top();
			que.pop();

			while (n2.count)
			{
				res += n1.c; 
				res += n2.c;

				n1.count--;
				n2.count--;
			}

			if(n1.count)
			que.push(n1);
		}

		if (que.size() == 1)
		{
			Node t = que.top();
			if (t.count > 1) return "";
			else res += t.c;
		}

		return res;
	}
};