Find the min and max number of substitutions

Question

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.

Example

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.

Task

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.

Answer 1

JavaScript (ES10),  169 168  161 bytes

Saved 7 bytes thanks to @KevinCruijssen

Takes the strings as (s)(t). Returns [min, max].

s=>t=>[[...Array(d=(g=(k,m=s.length,n=m,c)=>m*n?1+Math.min(g(k,m,n-1),g(k,--m,n),g(k-=c=s[m]!=t[--n],m,n)-!c):k?1/0:m-~n)())].flatMap((_,i)=>g(i)-d?[]:j=i)[0],j]

Try it online! (fast test cases)

Try it online! (a longer test case which may time out if TIO is overloaded)

Commented

Helper function \$g\$

\$g\$ is a function that computes the standard Levenshtein distance when it's called with \$k\$ undefined, or the edit distance with exactly \$k\$ substitutions when it's called with \$k\ge0\$. An additional offset of \$+1\$ is added to the result in both cases.

NB: It is presented separately for readability but must be defined within the scope of the main function so that the source string \$s\$ and the target string \$t\$ are defined.

g = (                         // g is a recursive function taking:
  k,                          //   k = allowed number of substitutions, or undefined
  m = s.length,               //   m = 1st pointer, initialized to the length of s
  n = m,                      //   n = 2nd pointer, initialized to the length of s
  c                           //   c = substitution cost
) =>                          //       (needs to be defined in the local scope)
  m * n ?                     // if both m and n are greater than 0:
    1 +                       //   add 1 to the final result
    Math.min(                 //   add the minimum of:
      g(k, m, n - 1),         //     recursive call for insertion with (m, n - 1)
      g(k, --m, n),           //     recursive call for deletion with (m - 1, n)
      g(                      //     recursive call for substitution:
        k -=                  //       set c if s[m - 1] is not equal to t[n - 1]
          c = s[m] != t[--n], //       and decrement k if c is set
        m, n                  //       use (m - 1, n - 1)
      ) - !c                  //     subtract 1 from the result if c is not set
    )                         //   end of Math.min()
  :                           // else (leaf node):
    k ?                       //   if k is not equal to 0 or NaN:
      1 / 0                   //     return +Infinity
                              //     (to make sure that this branch is not chosen)
    :                         //   else:
      m - ~n                  //     return m + n + 1

Main function

s => t =>                     // s = source string, t = target string
  [                           // the final result is a pair:
    [                         //   build an array containing:
      ...Array(d = g()),      //     d entries, where d = Levenshtein distance (+1)
    ]                         //
    .flatMap((_, i) =>        //   for each entry at position i in there:
      g(i)                    //     if the edit distance (+1) with i substitutions
      - d ?                   //     is not equal to d:
        []                    //       reject this entry
      :                       //     else:
        j = i                 //       append it to the array and copy i to j
    )[0],                     //   end of flatMap(); return the 1st entry (minimum)
    j                         //   followed by the last entry (maximum)
  ]                           // end of result