找到最大的字符串，使得 'a'、'b'、'c' 不连续

Question

Q3：- 我们给出了 \xe2\x80\x98a\xe2\x80\x99、\xe2\x80\x98b\xe2\x80\x99 和 \xe2\x80\x98c\xe2\x80\x99 的最大出现次数细绳。我们需要制作仅包含 \xe2\x80\x98a\xe2\x80\x99、\xe2\x80\x98b\xe2\x80\x99 和 \xe2\x80\x98c\xe2\x80\x99 的最大长度字符串，使得没有三个连续的字符是相同的。

\n\n

前任：-

\n\n

输入：- 3 3 3\n输出：- abcabcabc\n（可以有很多不同的输出）

\n\n

输入：- 5 5 3\n输出：- aabbcaabbcabc

\n

Answer 1

你可以使用这个算法：

作为预处理步骤，将每个字母（a、b 和 c）与其相应的最大频率相关联，以便您可以根据需要对这些字符频率对进行排序。

从空字符串开始并循环执行以下操作：

• 按频率递减对三个字母频率对进行排序
• 从排序列表中选择第一对并检查其频率。如果为零，则返回字符串
• 如果所选字符违反了同一字符不能连续重复 3 次的规则，则从排序列表中选择第二对并检查其频率。如果为零，则返回字符串
• 将选定的字符添加到字符串中，并降低其频率。
• 重复。

这是 JavaScript 中的交互式实现：

function largestSequence(freq) {
    // Create a data structure the links a frequency with a letter (a, b or c)
    let chars = [];
    for (let i = 0; i < 3; i++) {
        chars[i] = {
            freq: freq[i], 
            chr: "abc"[i]
        };
    }
    let s = "";
    while (true) {
        // Sort the three characters by decreasing frequency
        chars.sort((a, b) => b.freq - a.freq);
        let choice = chars[0]; // Choose the one with the highest frequency
        if (choice.freq === 0) break; // If no more character is avaiable, exit
        if (choice.chr + choice.chr === s.slice(-2)) {
            // If this character would violate the rule, choose the 
            // second one from the sorted list:
            choice = chars[1];
            if (choice.freq === 0) break; // If that character is not available, exit
        }
        choice.freq--; // Use this character
        s += choice.chr;
    }
    return s;
}

// I/O handling

let input = document.querySelector("input");
let output = document.querySelector("span");
input.oninput = function() {
    let freq = (input.value.match(/\d+/g) || []).map(Number);
    if (freq.length !== 3) {
        output.textContent = "(Please enter three integers)";
    } else {
        output.textContent = largestSequence(freq);
    }
};
input.oninput();

Frequencies for a, b, and c: <input value="3 3 3"><br>
Longest string: <span></span>