Remove letters while keeping strings unique

Question

Inspired by this wonderful (based on the number of views and votes) challenge, which, in my humble opinion, has way too few answers.

Given (by any means) a list of strings, return (by any means) a set of letters that, when removed from the given strings, leaves the total length of (what remains of) the strings as small as possible, while keeping each string unique and at least one character long.

Examples:

Given "Day" and "day"; return "ay", because the given strings will be "D" and "d" when the characters "ay" are removed.

Given "Hello World!", "Hello world.", and "Hello world"; return "Helo Wrd" gives because the strings will be "!", "w.", and "w" when the characters "Helo Wrd" (with a space) are removed.

Given "century", "decade", "year", "month", "week", "day", "hour", "minute", and "second"; return "centurdowi" because the given words will be "y", "a", "ya", "mh", "k", "ay", "h", "m", "s" when the characters "centurdowi" are removed.

The order and format of the returned set is not important.

• Luke: Your second case is wrong: "Helo Wrd" gives a total length of 4 with "!", "w." and "w".
• Adám: @Luke Thanks. I'll fix that. That shows that we need an algorithm, as doing it by hand is error prone.
• Luke: And for the third one, 'centurdowi' yields 'y', 'a', 'ya', 'mh', 'k', 'ay', 'h', 'm', 's' for a total length of 12.
• Adám: @Luke Thanks.
• Luke: +1 for using a challenge to help you in another challenge!

Answer 1

Haskell, (削除) 138 (削除ここまで) 130 bytes

import Data.List
c=concat
f i=snd$minimum[(length$c q,s)|s<-subsequences$nub$c i,q<-[map(filter(`notElem`s))i],nub q==q,all(>"")q]

Usage example: f ["century", "decade", "year", "month", "week", "day", "hour", "minute", "second"] -> "centurdoki".

This is a brute force approach.

 s<-subsequences$nub$c i -- concatenate input i to a single string, remove
 -- duplicates and make a list of all subsequences
 q<-[map(filter(...))i] -- remove chars appearing in subsequence s from all
 -- input words, call result q
 nub q==q -- keep those s where q has no duplicates (i.e. each
 -- resulting string is unique) and
 all(>"")q -- contains no empty strings
 (length$c q,s) -- make pairs from all kept s, where the first element
 -- is the combines length of all strings in q,
 -- second element is s itself
snd$minimum -- find minimum of those pairs and discard length

Edit: @Seeq helped me saving 8 bytes. Thanks!

• seequ: How about map(#s), so you don't need to flip notElem? EDIT: Or couldn't you just inline it?
• nimi: @Seeq: when call via map(#s), (#) must be defined as flip (filter . flip notElem). But of course inlining is far shorter. Thanks!

Answer 2

JavaScript (V8), 288 bytes

s=>(l=[...new Set(s.join``)],g=[],[...Array(2**l[L="length"])].map((x,i)=>l.filter((c,j)=>(i&2**j))).filter(x=>new Set(h=s.map(m=>[...m].filter(n=>!x.includes(n)).join``)).size==s[L]&&h.every(n=>n[L])&&g.push(h.reduce((a,b)=>a+b[L],0))).map(x=>[x,g.shift()]).sort((a,b)=>a[1]-b[1])[0][0])

Try it online!

Explanation:

s=> // Arrow function with argument s
(l=[...new Set(s.join``)], // Create a set l containing every character in s
 // Sets automatically remove duplicates
 // This converts the set back to an array, since arrays are easier to work with
g=[], // Create an empty array g
[...Array(2**l[L="length"])] // Create an array with length 2 ** number_of_inputs
.map((x,i)=>l.filter((c,j)=>(i&2**j))) // Populate the array with each combination of characters in l
.filter(x=>new Set(h=s.map(m=> // Filter the array (with each combination being x)
 [...m].filter(n=>!x.includes(n)) // For each inputted string, after removing the characters in x
 .join``)).size==s[L]&& // Check if the number of unique strings is equal to the number of inputs
 h.every(n=>n[L])&& // Ensure every string is at least one character
 g.push(h.reduce((a,b)=>a+b[L],0))) // Push the total length to g
.map(x=>[x,g.shift()]) // For each item x in the array, put it in an array with its corresponding item in g
.sort((a,b)=>a[1]-b[1])[0][0]) // Sort the array to find the shortest valid result, and output it

Answer 3

Pyth, 34

Takes input in the format ["century", "decade", "year", "month", "week", "day", "hour", "minute", "second"]. Golfing tips are appreciated, as always.

hh.mlsebfqlQl{eTf!}keTm,dm-kdQy{sQ

Answer 4

Pyth, 24 bytes

hols-RNQf<}kJ-RTQ{IJy{sQ

Try it online. Test suite.

Note that the last test case will take a little while to run.

Takes input in array form, like ["Day", "day"].

Another interesting one I found and isaacg improved (also 24 bytes):

-J{sQhlDsM.A#f{ITm-RdQyJ

• izzyg: I was able to reduce the second approach to 24 bytes: -J{sQhlDsM.A#f{ITm-RdQyJ here