Complexity of maximization of entropy of Hamming distance of bitstrings

We have a set of possible "key"s $$S$$ represented by bitstrings of length $$k$$. In other words, $$S$$ contains an arbitrary subset of all bitstrings of length $$k$$. For example, when $$k=3$$, it can be $$S = \{001, 010, 011, 000, 111\}$$. I would like to find a "guess", which maximizes the Hamming distance of itself and the possible keys, assuming that the keys in $$S$$ are drawn with equal possibility. For instance, say the guess is $$g = 001$$, then the Hamming distances are $$H(001, 001) = 0$$, $$H(001, 010) = 2$$, $$H(001, 011) = 1$$, $$H(001, 000) = 1$$, and $$H(001, 111) = 2$$. It follows that the entropy is $$E = -\left[\frac{1}{5}\log(\frac{1}{5})+\frac{2}{5}\log(\frac{2}{5})+\frac{2}{5}\log(\frac{2}{5})\right]$$. A superior guess would be $$g = 000$$ or $$g = 111$$, which actually maximizes the entropy. There will be multiple guesses that maximize the entropy, and finding any of them is enough.

I actually have two related questions:

1. How hard is it to find an optimal guess that maximizes the entropy? (In terms of N/NP/NPC/NPH, etc)
2. How hard is it to find the maximum entropy?

I have previously posted a related question on math.SE, and a comment suggested that full enumeration is probably the best algorithm I can get. The problem sounds even harder than the $$k$$-partition problem, so I guess it is NP-complete or NP-hard.