LeetCode 1405 Longest Happy String

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 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

题目大意：

给定三个整数代表abc的个数，生成一个字符串，字符串abc频数不能超过这3个数，不能有连续的aaa, bbb, ccc, 求此种字符串的最大长度

解题思路：

由第一个例子看出，先尽量用频数最多的字符，直到连续3个为止，然后再用次多的，如此反复做。这里用到最多和次多，所以考虑用Heap

解题步骤：

N/A

注意事项：

1. 每次选频数最高的字符，但若此字符已连续3次，选次高的，用heap。
2. 大于0的频数才加入到heap Line 4和Line 17
3. heapreplace等于heappop次高的和heappush最高的。既然要有次高，heap就不能为空

Python代码：

def longestDiverseString(self, a: int, b: int, c: int) -> str:
	res = ''
	heap = []
	if a > 0: # remember
		heapq.heappush(heap, (-a, 'a'))
	if b > 0:
		heapq.heappush(heap, (-b, 'b'))
	if c > 0:
		heapq.heappush(heap, (-c, 'c'))
	while heap:
		count, char = heapq.heappop(heap)
		if len(res) > 1 and res[-2] == res[-1] == char:
			if not heap:
				break
			count, char = heapq.heapreplace(heap, (count, char))
		res += char
		if count + 1:
			heapq.heappush(heap, (count + 1, char))
	return res

算法分析：

时间复杂度为O(n)，空间复杂度O(1)