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

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 对。因此，我们需要优化 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