1417. Reformat The String

Given alphanumeric string s. (Alphanumeric string is a string consisting of lowercase English letters and digits).

You have to find a permutation of the string where no letter is followed by another letter and no digit is followed by another digit. That is, no two adjacent characters have the same type.

Return the reformatted string or return an empty string if it is impossible to reformat the string.

Example 1:

Input: s = "a0b1c2"
Output: "0a1b2c"
Explanation: No two adjacent characters have the same type in "0a1b2c". "a0b1c2", "0a1b2c", "0c2a1b" are also valid permutations.

Example 2:

Input: s = "leetcode"
Output: ""
Explanation: "leetcode" has only characters so we cannot separate them by digits.

Example 3:

Input: s = "1229857369"
Output: ""
Explanation: "1229857369" has only digits so we cannot separate them by characters.

Example 4:

Input: s = "covid2019"
Output: "c2o0v1i9d"

Example 5:

Input: s = "ab123"
Output: "1a2b3"

Constraints:

• 1 <= s.length <= 500
• s consists of only lowercase English letters and/or digits.

---

给定一个包含字母和数字的字符串，输出将字母和数字交替排列的字符串，输出任意一个合法的即可。

简单题，首先先统计下字母和数字的个数，要让交替出现，则它们的个数之差必须小于2。然后把个数多的排前面，交替排列即可。完整代码如下：

class Solution {
public:
	string reformat(string s) {
		string alpha = "", digit = "";
		for (int i = 0; i < s.size(); ++i) {
			if (s[i] >= '0'&&s[i] <= '9')digit.push_back(s[i]);
			else alpha.push_back(s[i]);
		}

		int a = alpha.size(), d = digit.size();
		if (abs(a - d) >= 2)return "";
		string ans = "";
		int i = 0, j = 0;
		if (a > d) {
			while (i < a || j < d) {
				ans.push_back(alpha[i++]);
				if (j < d)ans.push_back(digit[j++]);
			}
		}
		else {
			while (i < a || j < d) {
				ans.push_back(digit[j++]);
				if (i < a)ans.push_back(alpha[i++]);
			}
		}
		return ans;
	}
};

本代码提交AC，用时12MS。