Java 11, 790 764 760 bytes
import java.util.*;t->n->{var S=new HashSet<String>();int m=n;for(;m>0;)p(S,"",t+"x".repeat(m--));for(var s:(HashSet<String>)S.clone())for(m=s.length()-n;m-->1;)S.add(s.substring(m));S.removeIf(s->d(1,s,t)!=n);for(var s:S)m=Math.max(d(0,s,t),m);return m;}void p(Set S,String p,String s){int l=s.length(),i=0;if(l<1)S.add(p);for(;i<l;)p(S,p+s.charAt(i),s.substring(0,i)+s.substring(++i));}int d(int f,String s,String t){int l=s.length()+1,L=t.length()+1,d[][]=new int[l][L],i=l,j,c,q,A,B;for(;i-->0;)d[i][0]=i;for(j=0;++j<L;)for(d[i=0][j]=j;++i<l;B=t.charAt(j-1),c=A==B?0:1,d[i][j]=q=Math.min(Math.min(d[i-1][j]+1,d[i][j-1]+1),d[i-1][j-1]+c),d[i][j]=f>0&i>1&j>1&&A==t.charAt(j-2)&s.charAt(i-2)==B?Math.min(q,d[i-2][j-2]+c):q)A=s.charAt(i-1);return d[l-1][L-1];}
Will golf it down (substantially I hope) from here.
Try it online.
Explanation:
General approach:
Input-String = t
and input-integer = n
in the explanation below.
- Generate all permutations of
t
with up to n
added characters, and add them to a Set
- For each permutation, add a substring with up to
n
removed characters to the Set as well
- Remove any String from this Set that does not have a Damerau-Levenshtein distance of
n
in comparison to t
- Calculate the Levenshtein distance of each remaining String in comparison to
t
- Take the maximum, which is our result
Code explanation:
import java.util.*; // Required import for the Set and HashSet
t->n->{ // Method with String and integer parameters and integer return-type
var S=new HashSet<String>(); // Create a String-Set
int m=n;for(;m>1;) // Loop `m` in the range [input-integer, 0):
p(S,"",t // Determine all permutations of the input-String
+"x".repeat(m--)); // With up to `m` additional "x" added
for(var s:(HashSet<String>)S.clone())
// Loop over all generated permutations:
for(m=s.length()-n;m-->1;) // Inner loop `m` in the range [permutation-length - input-integer, 1]:
S.add(s.substring(m)); // Add the permutation with the first `m` characters removed to the Set as well
// (NOTE: After these loops, `m` is 0 which we'll re-use later on)
S.removeIf(s-> // Now remove any permutation from this Set which:
d(1,s,t)!=n); // Does not have a DL-distance equal to the input-integer
for(var s:S) // Loop over all remaining Strings:
m=Math.max(d(0,s,t),m); // Determine the maximum L-distance
return m;} // And return that maximum L-distance as result
// Separated recursive method to get all permutations from a String
void p(Set S,String p,String s){ // Method with Set and two String parameters and no return-type
int l=s.length(), // Get the length of the input-String `s`
i=0; // Index-integer `i`, starting at 0
if(l<1) // If the length is 0:
S.add(p); // Add the prefix-String `p` to the Set
for(;i<l;) // Loop `i` in the range [0, length):
p(S,p+s.charAt(i), // Append the `i`'th character to the prefix-String `p`
s.substring(0,i)+s.substring(++i));}
// Remove the `i`'th character from the String `s`
// And do a recursive call
// Separated method to determine the DL or L distance of two Strings
int d(int f,String s,String t){ // Method with integer and two String parameters and String return-type
int l=s.length()+1, // Length `l` of the source-String + 1
L=t.length()+1, // Length `L` of the target-String + 1
d[][]=new int[l][L], // Create an integer matrix of those dimensions
i=l,j, // Index-integers
c,q,A,B; // Temp integers
for(;i-->0;) // Loop `i` in the range (`l`, 0]:
d[i][0]=i; // Set the `i,0`'th cell to `i` in the matrix
for(j=0;++j<L;) // Loop `j` in the range [0, `L`):
for(d[i=0][j]=j; // Set the `0,j`'th cell to `j` in the matrix
++i<l // Inner loop `i` in the range [0, `l`):
; // After every iteration:
B=t.charAt(j-1), // Set `B` to the `j-1`'th character of the target-String
c=A==B? // If the characters `A` and `B` are the same:
0 // Set `c` to 0
: // Else:
1, // Set `c` to 1
d[i][j]= // Set the `i,j`'th value to:
q=Math.min( // The minimum of:
Math.min( // The minimum of:
d[i-1][j]+1, // The `i-1,j`'th value + 1
d[i][j-1]+1), // And the `i,j-1`'th value + 1
d[i-1][j-1]+c), // And the `i-1,j-1`'th value + `c`
d[i][j]= // Then, set the `i,j`'th value to:
f>0 // If the given DL-flag is 1
&i>1&j>1 // And both `i` and `j` are at least 2
&&A // And the character `A`
==t.charAt(j-2)// equals the `j-2`'th character in the target-String
&s.charAt(i-2) // And the `i-2`'th character in the source-String
==B? // equals the character `B`:
Math.min( // Set the `i,j`'th value to the minimum of:
q, // The `i,j`'th value
d[i-2][j-2]+c) // And the `i-2,j-2`'th value + `c`
: // Else (the given DL-flag is 0):
q) // Leave the `i,j`'th value the same
A=s.charAt(i-1); // Set `A` to the `i-1`'th character of the source-String
return d[l-1][L-l];} // Return the `l-1,L-1`'th value as result
Hello
toHleol
is 3, so the example test case would need to be something based oneHlol
instead. As for the length 6 test case, a distance of 5 is possible (e.g.,rrKyypp
) \$\endgroup\$Hello
andeaHlol
have Levenshtein distance 4:Hello
→HeHlo
→eHlo
→eHlol
→eaHlol
\$\endgroup\$"Hello", 3 -> 5
. Are you sure it's 5? Otherwise my solution is wrong. \$\endgroup\$