「每日LeetCode」2022年2月7日

本文最后更新于：2023年3月19日 晚上

  1. 最长快乐字符串

1405. 最长快乐字符串

如果字符串中不含有任何 ‘aaa’，’bbb’ 或 ‘ccc’ 这样的字符串作为子串，那么该字符串就是一个「快乐字符串」。
给你三个整数 a，b ，c，请你返回 任意一个 满足下列全部条件的字符串 s：

  • s 是一个尽可能长的快乐字符串。
  • s 中 最多 有 a 个字母 ‘a’、b 个字母 ‘b’、c 个字母 ‘c’ 。
  • s 中只含有 ‘a’、’b’ 、’c’ 三种字母。

如果不存在这样的字符串 s ，请返回一个空字符串 “”。
​

示例 1：
输入：a = 1, b = 1, c = 7 输出：“ccaccbcc” 解释：“ccbccacc” 也是一种正确答案。
示例 2：
输入：a = 2, b = 2, c = 1 输出：“aabbc”
示例 3：
输入：a = 7, b = 1, c = 0 输出：“aabaa” 解释：这是该测试用例的唯一正确答案。
​

提示：

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

思路

模拟题意，贪心算法，如果应该取当前的元素为最多的元素，应该取 2 个，下一次取的还是该元素，那么该取第二大的元素 1 个。

解答

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
/**
 * @param {number} a
 * @param {number} b
 * @param {number} c
 * @return {string}
 */
var longestDiverseString = function (a, b, c) {
  const num = {
    a: { num: a, char: "a" },
    b: { num: b, char: "b" },
    c: { num: c, char: "c" },
  };

  // 计算最大最小中等的元素及其数量，计算剩余总数，及是否只剩下一个元素，及其对应字符及数量
  const calculate = () => {
    let total = 0,
      flag = false,
      onlyOne = true,
      restKey,
      restNum;

    const numArr = [];
    for (const key in num) {
      const element = num[key];
      numArr.push(num[key]);
      total += element.num;
      if (element.num) {
        // 是否只剩下一个元素，及其对应字符及数量
        if (!flag) {
          flag = true;
          restKey = key;
          restNum = element.num;
          continue;
        }
        if (flag) {
          onlyOne = false;
          restKey = "";
          restNum = 0;
        }
      }
    }

    numArr.sort((a, b) => a.num - b.num);

    return {
      min: numArr[0],
      middle: numArr[1],
      max: numArr[2],
      total,
      onlyOne,
      restKey,
      restNum,
    };
  };

  let res = "",
    count = 0,
    prev;

  while (true) {
    const { min, middle, max, total, onlyOne, restKey } = calculate();
    if (total <= 0 || onlyOne) break;

    let target;

    const array = [max, middle, min];

    for (let i = 0; i < array.length; i++) {
      const cur = array[i];
      const { num: curNum, char } = cur;
      if (char === prev || curNum <= 0) continue;
      target = cur;
      prev = char;

      let repeatNum = 1;

      // 如果是最大的，应该尽量取多，否则应该尽量取少的
      if (i === 0) repeatNum = curNum > 2 ? 2 : curNum;

      res += char.repeat(repeatNum);
      num[char].num -= repeatNum;
      break;
    }
  }

  const { onlyOne, restKey, restNum } = calculate();

  if (onlyOne) {
    const repeatNum = restNum > 2 ? 2 : restNum;
    return `${res}${restKey.repeat(repeatNum)}`;
  }

  return res;
};