给你两个s:N和K。伦狗对满足以下条件的字符串感兴趣:
- 字符串恰好有 N 个字符，每个字符要么是“A”，要么是“B”。
- 字符串 s 可以有 K 对 (i, j) (0 <= i < j <= N-1) 使得 s[i] = 'A' 和 s[j] = 'B'。
一串 N 个字符的 K 的最大值是多少？
最佳答案
我们可以假设“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
关于algorithm - 如何找到字符串可能具有的对的最大值？，我们在Stack Overflow上找到一个类似的问题： https://stackoverflow.com/questions/29456446/