[LeetCode] 1405. Longest Happy String

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 the longest 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 ，请返回一个空字符串 “”。

来源：力扣（LeetCode）
链接：https://leetcode-cn.com/problems/longest-happy-string
著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。

思路

这道题其实是 984 题的升级版，984 题只有 A 和 B 两个字母，这道题需要处理三个不同字母。

这道题的思路是贪心。这道题的贪心贪的就是尽可能先用剩余个数最多的字母。具体做法是我们用一个优先队列把三个字母及其次数放进去，次数最多的字母在堆顶。如果当前堆顶的字母已经在 res 里连续拼接过两次了，就需要再弹出下一个字母，直到堆空或者下一个字母不和当前堆顶的字母连续。

复杂度

时间O(n)
空间O(n)

代码

Java实现

class Solution {
	public String longestDiverseString(int a, int b, int c) {
		// ['a', count]
		PriorityQueue<int[]> queue = new PriorityQueue<>((x, y) -> y[1] - x[1]);
		if (a > 0) queue.offer(new int[] {0, a});
		if (b > 0) queue.offer(new int[] {1, b});
		if (c > 0) queue.offer(new int[] {2, c});

		StringBuilder sb = new StringBuilder();
		while (!queue.isEmpty()) {
			int[] cur = queue.poll();
			int n = sb.length();
			if (n >= 2 && sb.charAt(n - 1) - 'a' == cur[0] && sb.charAt(n - 2) - 'a' == cur[0]) {
				if (queue.isEmpty()) {
					break;
				}
				int[] next = queue.poll();
				sb.append((char) ('a' + next[0]));
				if (--next[1] > 0) {
					queue.offer(next);
				}
				queue.offer(cur);
			} else {
				sb.append((char) ('a' + cur[0]));
				if (--cur[1] > 0) {
					queue.offer(cur);
				}
			}
		}
		return sb.toString();
	}
}

相关题目

984. String Without AAA or BBB
1405. Longest Happy String