Java 中的最长快乐字符串

确定可以给定的三个整数a、b和c的最长快乐字符串。如果存在多个，则返回其中任何一个最长的快乐字符串。如果不存在这样的字符串，则返回空字符串“”。具有连续字符序列的字符串称为子字符串。

如果字符串str满足以下条件，则称其为快乐字符串：

• 字符串str中只包含字符“a”、“b”和“c”。
• 字符串str中不存在“aaa”、“bbb”或“ccc”这样的连续子串。
• 字符串str中的字符“a”最多可以出现a次。
• 字符串str中的字符“b”最多可以出现b次。
• 字符串str中的字符“c”最多可以出现c次。

示例 1

输入

int a = 1

int b = 1

int c = 7

输出

最长快乐字符串是“ccaccbcc”

解释

另一个合适的答案可能是“ccbccacc”。

示例 2

输入

int a = 7

int b = 1

int c = 0

输出

最长快乐字符串是“aabaa”

解释

在此情况下，这是唯一合适的答案。

方法：使用贪心算法

我们优先选择计数最多的两个字符。然而，对于计数不最多的字符，我们只取一个。计数较少的字符将被用作分隔符，这就是原因。为了尽可能获得最长的快乐字符串，我们希望贪婪地完成两件事。

• 尽可能多地使用计数最多的字符。
• 为了达到1，我们需要相同数量的分隔符。

在每次循环中将字母附加到结果后，我们重新评估哪个字母的计数最多。遵循1，如果它是最多的，则包含两个字符；否则，只附加一个。然后重新排列所有字母的计数。继续以相同的方式进行，直到用完所有计数较少的字母。

算法

步骤1：优先队列具有固定的顺序（Pair.cnt）。

步骤2：如果cnt大于零，则将字符和计数添加到PQ。

步骤3：如果大小大于两个（如果（p_one.cnt >= 2）），则附加两个字符（来自p_one）；否则，仅插入一个字符。

步骤4：如果大小大于两个且p_one.cnt小于p_two.cnt，则附加两个字符（来自p_two）。否则，只添加一个字符。

步骤5：在最后验证优先队列是否为空。如果不为空，则附加字符（如果字符不同）。

实施

文件名： HappyString.java

输出

 
The Longest Happy String is given by : ccaccbcc

复杂度分析

时间复杂度为O(a+b+c)，空间复杂度为O(a+b+c)。此复杂度分析假定为优先队列和相应字符a、b、c的计数相关的操作。