Hamming–Levenshtein gap of a string

¹ King Fahd University of Petroleum and Minerals, College of Computing and Mathematics Department of Mathematics, Dhahran, Saudi Arabia
² Department of Mathematics, Faculty of Mathematical, Physical and Natural Sciences of Tunis, University of Tunis El Manar, El-Manar 1, 2092, Tunisia

^* Corresponding author: This email address is being protected from spambots. You need JavaScript enabled to view it.

Received: 15 October 2025
Accepted: 23 April 2026

Abstract

Let u, v be strings over an alphabet Σ with |Σ| ≥ 2. Let L(u, v) be the Levenshtein distance and, when |u| = |v|, let H(u, v) be the Hamming distance. For equal-length strings, L(u, v) ≤ H(u, v). For u ∈ Σ*, define

hl(u): = max_{| v |=| u |} (H(u, v)−L(u, v)).

Ruth and Lladser [Discrete Math. 346 (2023) Paper No. 113310] showed that if the run-length of u is at most 2, then hl(u) = 0; conversely, hl(u) = 0 implies ρ(u) ≤ 2. For p ∈ {2, 3}, we characterize all strings u with hl(u) = |u| – p. We also identify two types of strings u such that hl(u) = |u| – 4.