How to determine the average of two strings?
Consider the $d(s,t)$ additions, deletions, and edits that transform $s$ in $t$.
Let $*$ be a new character.
Instead of inserting the prescribed character, insert $*$. Instead of deleting a character, change it to $*$. Instead of replacing a character with the prescribed character, replace it with $*$.

As an example, the edit distance between &quot;mars&quot; and &quot;toast&quot; is 4, and the corresponding edits are:

Change &quot;m&quot; in &quot;t&quot;
Add &quot;o&quot;
Leave &quot;a&quot; unchanged
Delete &quot;r&quot;
Leave &quot;s&quot; unchanged
Add &quot;t&quot;

Replace these steps with:

Change &quot;m&quot; in $*$
Add $*$
Leave &quot;a&quot; unchanged
Change &quot;r&quot; in $*$
Leave &quot;s&quot; unchanged
Add $*$

Applying these steps yields &quot;$**$a$*$s$*$&quot;.