# Find The Average String Between Two Strings

Inspired by this

Your task today: given two strings, find the string with the lowest maximum Levenshtein distance to the input strings. For example, using Steffan and Seggan, the average string will be Steggan. It is distance 2 from Steffan (replace the gg with ff), and 1 from Seggan (add a t). That gives it a maximum distance of 2.

Other constraints:

• If there are multiple possibilities, output any of them or all of them (duplicates are OK)
• The inputs are distinct
• The input will be given in uppercase or lowercase ASCII, you choose
• There will always be common letters in the inputs
• The outputs will only have letters from the inputs
• There will always be a solution satisfying the above constraints

As this is , shortest code in bytes wins.

## Testcases

seggan, steffan -> ['seffan', 'sefgan', 'segfan', 'stefgan', 'stegfan', 'steggan'] (2)
hello, ho -> ['hllo', 'hlo', 'helo', 'heo'] (2)
string, ring -> ['tring', 'sring'] (1),
aaa, aaaa -> ['aaa', 'aaaa'] (1)
abc, abcd -> ['abc', 'abcd', 'abd', 'abca', 'abcb', 'abcc'] (1)

• Can't abc, abcd also be abd? Aug 3 at 18:22
• @Steffan yeah, it can Aug 3 at 18:28
• I get that hello, ho is ["heo", "hlo", "hel", "elo", "heol", "helo", "hleo", "ehlo", "elho", "hll", "llo", "holl", "hllo"]. All of those have a max distance of 2 between hello, ho. Aug 3 at 20:43
• Also, I asked in the sandbox but no one responded. The test cases imply that the outputs can only contain letters in the inputs. Is that so? Several of these test cases could have way more possiblities if so. Aug 3 at 20:44
• @Steffan yes, it is so Aug 3 at 20:45

# Vyxal, 14 bytes

Þ∪Þx:ƛ□꘍GN;ÞMİ


Try it Online!

I think Þ∪ can be J, but that makes it so slow that it's practically impossible to run.

This is already really, really, really slow.

Þ∪Þx:ƛ□꘍GN;ÞMİ
Þ∪             # Get the multiset union of the two strings
Þx           # Get all combinations without replacement of all lengths and of all orders
:          # Duplicate (call this X)
ƛ         # Over each:
□꘍       #  For each of the inputs, get the Levenshthein distance between that input and this string
G      #  Get the maximum of that
N     #  Negate that
;    # Close map
ÞM  # Get the indices of maximal elements. (If Vyxal had an "indices of minimal elements" builtin, then negate could be removed.)
İ # Index this into X

• It's bad form to answer your own challenge so soon... Oh, wait, Aug 3 at 18:40

# 05AB1E, 9 bytes

JæΣ.L{R}н


Outputs one possible result.

Explanation:

J        # Join the (implicit) input-pair together to a single string
æ       # Pop and get the powerset of this string
Σ      # Sort it by:
.L    #  Get the Levenshtein distance of the two strings with the (implicit) input
{   #  Sort the pair from lowest to highest
R  #  Reverse it from highest to lowest
}н     # After the sort-by: leave the first result
# (which is output implicitly as result)


Note: if we'd use à (max) instead of {R, it would also give results where the Levensthein distance is [2,2] even if [1,2] are available. If we'd use just {, it would give results where the Levensthein distance is [0,3] over [1,2]. So using the {R ensures the minimum pair while prioritizing the maximum of the pair.

Although it works for the test cases, I'm not 100% sure if Jæ is always correct. Using an additional group-by (and uniquify) to get all results shows that Stegfan and Segfan aren't among them for example, since the powerset builtin uses characters of the joined string in order. This could be fixed by changing it to Jœ€æ˜ [+3 bytes] (powerset of each permutation of the joined string), but it becomes extremely slow and it'll timeout.

# Factor + lcs math.combinatorics, 123120 78 bytes

[ 2dup append all-subsets [ tuck [ levenshtein ] 2bi@ max ] 2with infimum-by ]


Attempt This Online!

-42 bytes(!) using the idea behind @KevinCruijssen's 05AB1E answer.

# Vyxal, 9 bytes

∑ṗµ?꘍sṘ;h


Try it Online!

Port of Kevin Cruijssen's answer, go upvote that!

# Python, 150 bytes

n=lambda A,B:{a[:x]+y+a[z:]for a in A for x in range(len(a)+1)for z in[x,x+1]for b in B for y in[*b,""]}
f=lambda A,B:(N:=n(A,B))&(M:=n(B,A))or f(N,M)

Attempt This Online!