1405. 最长快乐字符串

🟠   🔖  贪心 字符串 堆（优先队列）  🔗 力扣 LeetCode

题目

A string s is called happy if it satisfies the following conditions:

• s only contains the letters 'a', 'b', and 'c'.
• s does not contain any of "aaa", "bbb", or "ccc" as a substring.
• s contains at most a occurrences of the letter 'a'.
• s contains at most b occurrences of the letter 'b'.
• s contains at most c occurrences of the letter 'c'.

Given three integers a, b, and c, return thelongest possible happy string. If there are multiple longest happy strings, return any of them. If there is no such string, return the empty string"".

A substring is a contiguous sequence of characters within a string.

Example 1:

Input: a = 1, b = 1, c = 7

Output: "ccaccbcc"

Explanation: "ccbccacc" would also be a correct answer.

Example 2:

Input: a = 7, b = 1, c = 0

Output: "aabaa"

Explanation: It is the only correct answer in this case.

Constraints:

• 0 <= a, b, c <= 100
• a + b + c > 0

题目大意

如果字符串中不含有任何 'aaa'，'bbb' 或 'ccc' 这样的字符串作为子串，那么该字符串就是一个「快乐字符串」。

给你三个整数 a，b ，c，请你返回 任意一个 满足下列全部条件的字符串 s：

• s 是一个尽可能长的快乐字符串。
• s 中 最多 有a 个字母 'a'、b 个字母 'b'、c 个字母 'c' 。
• s 中只含有 'a'、'b' 、'c' 三种字母。

如果不存在这样的字符串 s ，请返回一个空字符串 ""。

示例 1：

输入： a = 1, b = 1, c = 7

输出： "ccaccbcc"

解释： "ccbccacc" 也是一种正确答案。

示例 2：

输入： a = 2, b = 2, c = 1

输出： "aabbc"

示例 3：

输入： a = 7, b = 1, c = 0

输出： "aabaa"

解释： 这是该测试用例的唯一正确答案。

提示：

• 0 <= a, b, c <= 100
• a + b + c > 0

解题思路

这个问题可以归类为贪心算法。核心思路是优先使用次数最多的字符，但要避免产生连续三个相同的字符。

1. 模拟构建字符串： 维护三个变量 a, b, 和 c，分别表示每个字符的剩余次数。
2. 排序选择最大字符：每次都对按照前剩余次数从大到小排序，优先选择剩余次数最多的字符进行拼接。
3. 贪心策略：每次选择剩余次数最多的字符加入结果，如果该字符已经连续出现两次，则选择剩余次数第二多的字符，确保不会连续出现三个相同字符。
4. 停止条件：当不能再添加任何字符时，即无法选择下一个合法字符（例如所有字符都已经使用完，或者剩下的字符会导致违背"连续不重复三次"的规则），则停止构建。

复杂度分析

• 时间复杂度：O(n)，其中 n 是 a + b + c，最多进行 a + b + c 次字符加入操作，每次加入时只需进行最多三次的比较和选择。
• 空间复杂度：O(n)，构建了一个最大长度为 a + b + c 的结果字符串。

代码

/**
 * @param {number} a
 * @param {number} b
 * @param {number} c
 * @return {string}
 */
var longestDiverseString = function (a, b, c) {
	let str = '';
	let chars = [
		{ char: 'a', count: a },
		{ char: 'b', count: b },
		{ char: 'c', count: c }
	];

	while (true) {
		// 按照 count 从大到小排序
		chars.sort((a, b) => b.count - a.count);

		let added = false;
		for (let i = 0; i < 3; i++) {
			let char = chars[i].char;
			if (chars[i].count == 0) break;

			// 如果最后两个字符和当前字符一样，跳过
			if (
				str.length >= 2 &&
				str[str.length - 2] == char &&
				str[str.length - 1] == char
			) {
				continue;
			}

			// 否则将它加到 str 末尾
			str = str + char;
			chars[i].count--;
			added = true;
			break;
		}

		// 当不能再添加任何字符时，停止循环
		if (!added) break;
	}
	return str;
};

相关题目

题号	标题	题解	标签	难度	力扣
767	重构字符串		贪心 哈希表 字符串 3+	🟠	🀄️ 🔗