“This is the 14th day of my participation in the First Challenge 2022. For details: First Challenge 2022.”

A string is a “happy string” if it does not contain any strings like ‘AAA’, ‘BBB’ or ‘CCC’ as substrings.

Given three integers a, b, and c, return any string S that meets all of the following criteria:

  • sIs as long a happy string as possible.
  • s 中most 有aA letter'a',bA letter'b',cA letter'c' 。
  • sOnly contains'a','b' 、'c'Three letters.

If no such string s exists, return an empty string “”.

Example 1:

Input: A = 1, b = 1, c = 7 Output: "ccaccbcc" Explanation: "ccbccacc" is also a correct answer.Copy the code

Example 2:

Input: a = 2, b = 2, c = 1Copy the code

Example 3:

Input: A = 7, b = 1, c = 0 Output: "aabaa" Explanation: This is the only correct answer to this test case.Copy the code

greedy

The problem is to find the longest happy string that does not contain three consecutive letters of the same character. To find the longest string, we can use the following greedy strategy:

  • If possible, use the largest number of letters first, because the more letters of the same type are left at the end, the more likely it is to have the same letters consecutively. If there are unselected letters left after constructing the longest happy string, the remaining letters must be of the same type and have the largest total number of letters.
  • We start with the largest number of letters, and if we find that adding the current letter will result in three consecutive letters, we skip the current letter until we find one that can be added. In fact, only one of the most and least numerous letters is selected at a time.
  • If you try all the letters and can’t add them, you just exit, and the resulting string is the longest happy string.
var longestDiverseString = function(a, b, c) { const res = []; const arr = [[a, 'a'], [b, 'b'], [c, 'c']]; while (true) { arr.sort((a, b) => b[0] - a[0]); let hasNext = false; for (const [i, [c, ch]] of arr.entries()) { if (c <= 0) { break; } const m = res.length; if (m >= 2 && res[m - 2] === ch && res[m - 1] === ch) { continue; } hasNext = true; res.push(ch); arr[i][0]--; break; } if (! hasNext) { break; } } return res.join(''); };Copy the code

Complexity analysis

  • Time complexity: O ((a + b + c) x Clog ⁡ c) O ((a + b + c) x Clog ⁡ c) O ((a + b + c) x Clog ⁡ c), among them a, b, ca, b, ca, b, c, for a given integer c said the kinds of letters, in the ontology c = 3 c = 3 c = 3. Each time you select a letter from the selected letter, you need to sort it once. The time complexity is O(Clog⁡C)O(Clog⁡C)O(Clog⁡C). You need to select a maximum of a+ B + CA + B + CA + B + C.
  • Space complexity: O(C)O(C)O(C) in this case, C=3. C = 3. C = 3. O(C)O(C)O(C) is needed to store the current count of letters.