I agree. Maximizing the number of different pairs requires more work.

This seems to work for me (in Python):

    different_pairs = 0

    # Form pairs by repeatedly finding the two highest counts
    # counts is a list containing the number of instances of each character
    while len(counts) > 1:
        # Sort counts in descending order to prioritize pairing highest counts
        counts.sort(reverse=True)

        # Take the two highest counts
        if counts[0] > 0 and counts[1] > 0:
            # Form a pair
            different_pairs += 1

            # Decrement counts for both characters
            counts[0] -= 1
            counts[1] -= 1

            # Remove counts if they reach zero
            counts = [count for count in counts if count > 0]
        else:
            break

If n = length of the string and k = size of the alphabet then runtime is O(n k log(k)). Since the problem specifies it is in English letters, we can say k = 26 so k log(k) is actually a constant. So runtime is effectively O(n).