如何找到字符串能够拥有的最大值对数？

Question

你被给定两个参数：N 和 K。Lun 是只狗，他对满足以下条件的字符串感兴趣：

• 字符串恰好有 N 个字符，每个字符是 'A' 或 'B'。
• 字符串 s 最多包含 K 对 (i, j)（0 <= i < j <= N-1），使得 s[i] = 'A' 且 s[j] = 'B'。

那么长度为 N 的字符串 s 最多包含几对 (i, j) 呢？

- user3703441

Answer 1

我们可以假设'A'在'B'之前，因为在每个解决方案中，我们可以将'A'重新排序到字符串的开头，并获得相同或更大数量的配对。例如，'BAA'没有配对，'ABA'有一个配对，'AAB'有两个配对。

如果我们在开头有a A和b B，那么我们有K = a * b个配对。因此，我们需要优化K = a * b，并且a + b = N。

如果N是偶数，则有：

a = b = N / 2，K = N * N / 4

如果N是奇数，则有：

a = (N - 1) / 2，b = (N + 1) / 2，K = (N * N - 1) / 4

- JuniorCompressor

---

我不这么认为，假设我们有一个包含5个字符的字符串。根据你的解决方案，最大的K值是5，但是我们可以找到一个K值为6的字符串：AAABB。 - Fouad Wahabi

@FouadWahabi，N为奇数：k = ((NN)-1)/4 而非 k = (N(N-1))/4。 - user3703441

Answer 2

这个看起来怎么样？

function createString(N, K) {
    const res = Array(N).fill('a');
    let i = 1, start = 1, end = N, pairs = 0;

    while (pairs < K && start < end) {
        res[i - 1] = 'a';
        res[i] = 'b';
        pairs++;
        i++;

        if (i === end) {
            start++;
            end--;
            i = start;
        }
    }

    return pairs < K ? '' : res.join('');
}

- Vyacheslav A.