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.

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!

Answer 2

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 3

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