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.


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.

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

4 Answers 4


Haskell, 138 130 bytes

import Data.List
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!

  • \$\begingroup\$ How about map(#s), so you don't need to flip notElem? EDIT: Or couldn't you just inline it? \$\endgroup\$
    – seequ
    Commented Dec 22, 2015 at 9:57
  • \$\begingroup\$ @Seeq: when call via map(#s), (#) must be defined as flip (filter . flip notElem). But of course inlining is far shorter. Thanks! \$\endgroup\$
    – nimi
    Commented Dec 22, 2015 at 10:07

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!


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

Pyth, 34

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


Pyth, 24 bytes


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):

  • \$\begingroup\$ I was able to reduce the second approach to 24 bytes: -J{sQhlDsM.A#f{ITm-RdQyJ here \$\endgroup\$
    – isaacg
    Commented Dec 22, 2015 at 9:10

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.