The Levenshtein distance between two strings is the minimum number of single character insertions, deletions and substitutions needed to transform one string into the other. Let us call insertions, deletions and substitutions "edit operations". We will say that any sequence of \$k\$ edit operations that transforms one string into another one is optimal if \$k\$ is also the Levenshtein distance between the two strings.
For example, take the strings \$ab\$ and \$ba\$. The optimal sequence of edit operations "insert \$b\$ at index 0", "delete the final character" transforms \$ab\$ into \$ba\$. However a different optimal sequence "substitute the first character for a \$b\$", "substitute the second character for an \$a\$" also transforms \$ab\$ into \$ba\$. In general there may be many different optimal sequences of edit operations for a given pair of strings.
For an optimal sequence of edit operations we are interested in counting the number of substitutions in the sequence. In particular, for a given pair of strings, we want to count the smallest possible number of substitutions in an optimal sequence of edit operations and also the largest possible. We will assume that both strings have the same length.
0000 0000 . In this case every optimal sequence has length 0 and so min = max = 0. 0010 1001 . Levenshtein distance 2 by one insertion and one deletion. min = max = 0. 1100 1110 . Levenshtein distance 1. min = max = 1. There is no optimal sequence with an insertion or deletion. 1010 1100 . Levenshtein distance 2. min = 0. max = 2. 1010 0111 . Levenshtein distance 3. min = 1. max = 3. 0011 1100 . Levenshtein distance 4. min = 0. max = 4. 10000011 11110100. Levenshtein distance 6. min = 2. max = 6. 000111101110 100100111010. Levenshtein distance 5. min = 1. max = 5. 0011011111001111 1010010101111110. Levenshtein distance 7. min = 3. max = 7. 0010100001111111 0010010001001000. Levenshtein distance 7. min = 5. max = 7. 10100011010010110101011100111011 01101001000000000111101100000000. Levenshtein distance 15. min = max = 9. 11011110011010110101101011110100 00100010101010111010000000001110. min = 8. max = 12. 32123323033013011333111032331323 13100313103110123321321211233032. min = 6. max = 14. 17305657112546416613111655660524 23146332512152524313021536474017. min = 11. max = 21.
For a given pair of strings of the same length, output the minimum and maximum number of substitutions in an optimal sequence of edit operations for those two strings.
You can assume the input is given in any convenient form you choose and may similarly provide the output in any way that is convenient for you.