  We study the query complexity of a permutation-based variant of the guessing
game Mastermind. In this variant, the secret is a pair $(z,\pi)$ which consists
of a binary string $z \in \{0,1\}^n$ and a permutation $\pi$ of $[n]$. The
secret must be unveiled by asking queries of the form $x \in \{0,1\}^n$. For
each such query, we are returned the score \[ f_{z,\pi}(x):= \max \{ i \in
[0..n]\mid \forall j \leq i: z_{\pi(j)} = x_{\pi(j)}\}\,;\] i.e., the score of
$x$ is the length of the longest common prefix of $x$ and $z$ with respect to
the order imposed by $\pi$. The goal is to minimize the number of queries
needed to identify $(z,\pi)$. This problem originates from the study of
black-box optimization heuristics, where it is known as the
\textsc{LeadingOnes} problem.
  In this work, we prove matching upper and lower bounds for the deterministic
and randomized query complexity of this game, which are $\Theta(n \log n)$ and
$\Theta(n \log \log n)$, respectively.
