Relation between edit distances over different alphabets Assume we have two strings $S_1$ and $S_2$ of lengths $cn$ and $cm$ bits resepctively for some $c\in\Bbb N$.

Assume that the Levenshtein distance (minimum number of single-character edits (i.e. insertions, deletions or substitutions)) between $S_1$ and $S_2$ over binary alphabet is $L(2)$.

For any $b$ such that $b&gt;1$ and $b|c$ consider the strings $S_1$ and $S_2$ over alphabet $\{0,1,\dots,2^b-1\}$. Assume the Levenshtein distance between $S_1$ and $S_2$ over $b$-ary alphabet is $L(2^b)$.

Is there any relation between $L(2)$ and $L(2^b)$ in general?

Can we say anything for LCS (minimum number of insertions or deletions) distance as well?
Obviously, $L(2^b) \leq L(2)$.

The Levenshtein distance is at most the length of the longest string, so $L(2^b) \leq \max(cn,cm) / b$ whereas $L(2) \leq \max(cn,cm)$.

You cannot avoid $L(2^b)(S_1,S_2) = L(2)(S_1,S_2)$ when $L(2)(S_1,S_2) \leq \max(cn,cm) / b$:
consider for instance $b = c = 2$, $S_1 = 0^{2n}$ and $S_2 = (01)^{p} (00)^{n-p}$.

When $L(2)(S_1,S_2) &gt; \max(cn,cm) / b$, you cannot avoid $L(2^b)(S_1,S_2) = \max(cn,cm) / b$.
Consider for instance $b = c = 2$, $S_1 = 0^{2n}$ and $S_2 = 1^{2n}$.