You are given two s: N and K. Lun the dog is interested in strings that satisfy the following conditions:
What's the maximum value of K a string of N characters could have?
We can assume that 'A' are before 'B', since in each solution we can reorder the 'A' to the beginning of the string and get the same or bigger number of pairs. For example 'BAA' has no pairs, 'ABA' has one pair and 'AAB' has two pairs.
If we have a
A
at the beginning and b
B
then we have K = a * b
pairs. So we need to optimise K = a * b
given that a + b = N
.
If N
is even then we have:
a = b = N / 2, K = N * N / 4
and if N
is odd we have:
a = (N - 1) / 2, b = (N + 1) / 2, K = (N * N - 1) / 4
Collected from the Internet
Please contact [email protected] to delete if infringement.
Comments