A string is called happy if it does not have any of the strings 'aaa', 'bbb' or 'ccc' as a substring.

    Given three integers a, b and c, return any string s, which satisfies following conditions:

    • s is happy and longest possible.
    • s contains at most a occurrences of the letter 'a', at most b occurrences of the letter 'b' and at most c occurrences of the letter 'c'.
    • swill only contain 'a', 'b' and 'c' letters.

    If there is no such string s return the empty string "".

    Example 1:

    1. Input: a = 1, b = 1, c = 7
    2. Output: "ccaccbcc"
    3. Explanation: "ccbccacc" would also be a correct answer.

    Example 2:

    1. Input: a = 2, b = 2, c = 1
    2. Output: "aabbc"

    Example 3:

    1. Input: a = 7, b = 1, c = 0
    2. Output: "aabaa"
    3. Explanation: It's the only correct answer in this case.

    Constraints:

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

    题意

    一个不包含”aaa”或”bbb”或”ccc”子串的字符串被称为Happy String。要求用a个’a’、b个’b’、c个’c’组合成一个最长的Happy String。

    思路

    贪心。为了使得到的字符串最长，每次拼接字符时都应该尽可能消耗掉剩余数量最多的字符。步骤为：每次选出当前剩余数量最多的字符x和第二多的字符y，若x数量大于等于2，则拼接上2个x，否则拼接上1个x；此时判断x拼接后剩余数量是否比y多，若比y多则拼接上一个y，否则不需要拼接y，进入下一个循环。该步的关键思想为：每一次循环尽可能消耗掉剩余数量最多的字符，然后视情况拼接一个数量第二多的字符来当作分隔字符，以保证在下一个循环中选出的数量最多的字符x一定可以尽可能多地拼接在结果字符串的末尾(即不会出现拼接两个字符x会导致三个连续x的情况)。

    解题思路及递归解法出处为LeetCode论坛解答 votrubac - C++/Java a >= b >= c。

    代码实现 - 递归

    1. class Solution {
    2.     public String longestDiverseString(int a, int b, int c) {
    3.         return helper(a, b, c, "a", "b", "c");
    4.     }
    6.     private String helper(int lg, int md, int sm, String lgc, String mdc, String smc) {
    7.         if (lg < md) return helper(md, lg, sm, mdc, lgc, smc);
    8.         if (md < sm) return helper(lg, sm, md, lgc, smc, mdc);
    9.         if (md == 0) return lgc.repeat(Math.min(lg, 2));
    11.         int lgToUse = Math.min(lg, 2);
    12.         int mdToUse = lg - lgToUse < md ? 0 : 1;
    13.         return lgc.repeat(lgToUse) + mdc.repeat(mdToUse) + helper(lg - lgToUse, md - mdToUse, sm, lgc, mdc, smc);
    14.     }
    15. }

    代码实现 - 优先队列

    1. class Solution {
    2.     public String longestDiverseString(int a, int b, int c) {
    3.         Queue<Pair> q = new PriorityQueue<>((x, y) -> y.count - x.count);
    4.         StringBuilder sb = new StringBuilder();
    5.         if (a > 0) q.offer(new Pair('a', a));
    6.         if (b > 0) q.offer(new Pair('b', b));
    7.         if (c > 0) q.offer(new Pair('c', c));
    9.         while (q.size() > 1) {
    10.             Pair first = q.poll();
    11.             Pair second = q.poll();
    13.             sb.append(first.letter);
    14.             first.count--;
    15.             if (first.count > 0) {
    16.                 sb.append(first.letter);
    17.                 first.count--;
    18.             }
    20.             if (second.count <= first.count) {
    21.                 sb.append(second.letter);
    22.                 second.count -= 1;
    23.             }
    25.             if (first.count>0) q.offer(first);
    26.             if (second.count>0) q.offer(second);
    27.         }
    29.         if (!q.isEmpty()) {
    30.             Pair last = q.poll();
    31.             sb.append(last.letter);
    32.             last.count--;
    33.             if (last.count > 0) {
    34.                 sb.append(last.letter);
    35.             }
    36.         }
    38.         return sb.toString();
    39.     }
    41.     class Pair {
    42.         char letter;
    43.         int count;
    45.         public Pair(char letter, int count) {
    46.             this.letter = letter;
    47.             this.count = count;
    48.         }
    49.     }
    50. }