As has been pointed out, this problem is similar to the more commonly known edit distance problem (underlying the Levenshtein distance). It also has commonalities with, for example, Dynamic Time Warping distance (the duplication, or “stuttering,” in your last requirement).
Steps toward dynamic programming
My first attempt at a recursive decomposition along the lines of Levenshtein distance and Dynamic Time Warping Distance was something like the following (for $x=x_1\ldots x_n$ and $y=y_1\ldots y_m$), with $d(x,y)$ being set to
$$
\min
\begin{cases}
d(x,y_1\ldots y_{m-1})+1 & &\text{▻ Add letter at end}\\
d(x,y_2\ldots y_m)+1 & & \text{▻ Add letter at beginning}\\
d(x,y_1\ldots y_{m/2})+1 & \text{if $y=y_1\ldots y_{m/2}y_1\ldots y_{m/2}$}
& \text{▻ Doubling}\\
d(x_1\ldots x_{n/2},y)+1 & \text{if $x=x_1\ldots x_{n/2}x_1\ldots x_{n/2}$}
& \text{▻ Halving}\\
d(x_1\ldots x_n,y) + 1 && \text{▻ Deletion}\\
d(x_1\ldots x_{n-1},y_1\ldots y_{m-1}) & \text{if $y_n = y_m$}
& \text{▻ Ignoring last elt.}\\
\end{cases}
$$
Here, the last option basically says that converting FOOX to BARX is equivalent to converting FOO to BAR. This means that you could use the “add letter at end” option to achieve the stuttering (duplication) effect, and the deletion at an point. The problem is that it automatically lets you add an arbitrary character in the middle of the string as well, something you probably don't want. (This “ignoring identical last elements” is the standard way to achieve deletion and stuttering in arbitrary positions. It does make prohibiting arbitrary insertions, while allowing additions at either end, a bit tricky, though…)
I've included this breakdown even though it doesn't do the job completely, in case someone else can “rescue” it, somehow—and because I use it in my heuristic solution, below.
(Of course, if you could get a breakdown like this that actually defined your distance, you'd only need to add memoization, and you'd have a solution. However, because you're not just working with prefixes, I don't think you could use just indexes for your memoization; you might have to store the actual, modified strings for each call, which would get huge if your strings are of substantial size.)
Steps toward a heuristic solution
Another approach, which might be easier to understand, and which could use quite a bit less space, is to search for the shortest “edit path” from your first string to your second, using the $A^\ast$ algorithm (basically, best-first branch-and-bound). The search space would be defined directly by your edit operations. Now, for a large string, you would get a large neighborhood, as you could delete any character (giving you a neighbor for each potential deletion), or duplicate any character (again, giving you a linear number of neighbors), as well as adding any character at either end, which would give you a number of neighbors equal to twice the alphabet size. (Just hope you're not using full Unicode ;-) With such a large fanout, you might achieve quite a substantial speedup using a bidirectional $A^*$, or some relative.
In order to make $A^*$ work, you'd need a lower bound for the remaining distance to your target. I'm not sure if there's an obvious choice here, but what you could do is implement a dynamic programming solution based on the recursive decomposition I gave above (again with possible space issues if your strings are very long). While that decomposition doesn't exactly compute your distance, it is guaranteed to be a lower bound (because it's more permissive), which means it'll work as a heuristic in $A^*$. (How tight it'll be, I don't know, but it would be correct.) Of course, the memoization of your bound function could be shared across all calculations of the bound during your $A^*$ run. (A time-/space-tradeoff there.)
So…
The efficiency of my proposed solution would seem to depent quite a bit on (1) the lengths of your strings, and (2) the size of your alphabet. If neither is huge, it might work. That is:
- Implement the lower bound to your distance using my recursive decomposition and dynamic programming (for example, using a memoized, recursive function).
- Implement $A^*$ (or bidirectional $A^*$) with your edit operations as “moves” in the state-space, and the dynamic programming-based lower bound.
I can't really give any guarantees for how efficient it'd be, but it should be correct, and it would probably be a lot better than a brute-force solution.
If nothing else, I hope this gives you some ideas for further investigations.
A
andB
in @reinerpost's sequence.) $\endgroup$