Compute the edit distance between two words in which substitution is not allowed
You can use the same dynamic programming algorithm as the one for the Levenshtein distance with a bit of modifications.
Let $u=u_1…u_n$ and $v=v_1…v_m$ be two words. We want to build a $(n+1)\times(m+1)$ matrix $M$ such that for $0\leq i\leq n$ and $0\leq j \leq m$, $M[i][j]$ is the edit distance between $u_1…u_i$ (or $\varepsilon$ if $i = 0$) and $v_1…v_j$. The answer is then $M[n][m]$.
Now note that for $0&lt; i\leq n$ and $0&lt; j \leq m$:

if $u_i = v_j$, then $M[i][j] = \min\left\{\begin{array}{rl}M[i-1][j]+1 &amp; (\text{deletion of }u_i)\\M[i][j-1]+1&amp;(\text{insertion of }v_j)\\M[i-1][j-1] &amp; (\text{no modification})\end{array}\right.$
otherwise, $M[i][j] = \min\left\{\begin{array}{rl}M[i-1][j]+1 &amp; (\text{deletion of }u_i)\\M[i][j-1]+1&amp;(\text{insertion of }v_j)\end{array}\right.$