Charge and reduce: A fixed‐parameter algorithm for String‐to‐String Correction

String distance problems typically ask for a minimum number of permitted operations to transform one string into another. Such problems find application in a wide variety of areas, including error‐correcting codes, parsing theory, speech recognition, and computational biology, to name a few. Here we consider a classic string distance problem, the $\mathcal{N}P$ ‐complete String‐to‐String Correction problem, first studied by Wagner some 35 years ago. In this problem, we are asked whether it is possible to transform string $x$ into string $y$ with at most $k$ operations on $x$ , where permitted operations are single‐character deletions and adjacent character exchanges. We prove that String‐to‐String Correction is fixed‐parameter tractable, for parameter $k$ , and present a simple fixed‐parameter algorithm that solves the problem in $\mathcal{O}\left(2^{k}n\right)$ time. We also devise a bounded search tree algorithm, and introduce a bookkeeping technique that we call charge and reduce. This leads to an algorithm whose running time is $\mathcal{O}\left(1.6181^{k}n\right)$ .