  In the trace reconstruction problem, one observes the output of passing a
binary string $s \in \{0,1\}^n$ through a deletion channel $T$ times and wishes
to recover $s$ from the resulting $T$ "traces." Most of the literature has
focused on characterizing the hardness of this problem in terms of the number
of traces $T$ needed for perfect reconstruction either in the worst case or in
the average case (over input sequences $s$). In this paper, we propose an
alternative, instance-based approach to the problem. We define the "Levenshtein
difficulty" of a problem instance $(s,T)$ as the probability that the resulting
traces do not provide enough information for correct recovery with full
certainty. One can then try to characterize, for a specific $s$, how $T$ needs
to scale in order for the Levenshtein difficulty to go to zero, and seek
reconstruction algorithms that match this scaling for each $s$. For a class of
binary strings with alternating long runs, we precisely characterize the
scaling of $T$ for which the Levenshtein difficulty goes to zero. For this
class, we also prove that a simple "Las Vegas algorithm" has an error
probability that decays to zero with the same rate as that with which the
Levenshtein difficulty tends to zero.
