如何找到字符串可能具有的对的最大值？

Question

给你两个s：N和K。伦狗对满足以下条件的字符串感兴趣：

该字符串恰好有 N 个字符，每个字符要么是 'A'，要么是 'B'。
字符串 s 可以有 K 对 (i, j) (0 <= i < j <= N-1) 这样 s[i] = 'A' 和 s[j] = 'B'。

一串 N 个字符的 K 的最大值是多少？

Answer 1

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

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

如果 N 是偶数，那么我们有：

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

如果 N 是奇数，我们有：

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

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('');
}

如何找到字符串可能具有的对的最大值？

How to find the maximum value of pairs a string could have?

algorithm

optimization

max