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

preface

Today’s title is medium, making happy strings on your first day at work, Leetcode really has you…

A daily topic

Today’s daily question 1405. The longest happy string, of medium difficulty

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

  • S is a happy string as long as possible.

  • S contains a maximum of a letters’ A ‘, B letters ‘b’, and C letters’ C ‘.

  • S contains only ‘A’, ‘b’ and ‘C’.

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

 

Example 1:

Enter: a =1, b = 1, c = 7Output:"ccaccbcc"Explanation:"ccbccacc"It's also the right answer.Copy the code

Example 2:

Enter: a =2, b = 2, c = 1Output:"aabbc"
Copy the code

Example 3:

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

Tip:

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

Answer key

greedy

According to the requirements of the subject, we need to give us the number of the three letters in the portfolio is the longest string, we can use greedy thinking, as much as possible with the current the most letters, because the string need not be repeated three characters, so we can under the premise that meet the conditions, using the current most letters as much as possible. We can then store the successful data in an array and then concatenate them.

  1. Let’s use a two-dimensional array to store the number of each letter given:
const arr = [
[a, "a"],
[b, "b"],
[c, "c"]];Copy the code

  1. The loop is then looped and an exit condition is defined: let hasNext = false. This value will be changed to true only if the above condition is met to proceed to the next step.

  2. If the largest number of letters in the current loop meets the condition that there are no more than three repetitions, change the loop condition to true, add the answers to the array, and decrease the number of letters by one. If not, exit and loop through the second largest letter, and so on.

  3. Finally, concatenate the resulting array of answers, which is the longest happy string the problem needs.

/ * * *@param {number} a
 * @param {number} b
 * @param {number} c
 * @return {string}* /
var longestDiverseString = function (a, b, c) {
  const ans = [];
  const arr = [
    [a, "a"],
    [b, "b"],
    [c, "c"]];while (true) {
    arr.sort((a, b) = > b[0] - a[0]);
    let hasNext = false;
    for (const [i, [key, val]] of arr.entries()) {
      if (key <= 0) {
        break;
      }
      n = ans.length;
      if (n >= 2 && ans[n - 2] === val && ans[n - 1] === val) {
        continue;
      }
      hasNext = true;
      ans.push(val);
      arr[i][0]--;
      break;
    }
    if(! hasNext) {break; }}return ans.join("");
};
Copy the code