For this challenge you need to make a given word by concatenating "pieces" (a.k.a contiguous substrings) from other words. Given a word and a list of words as input, output the fewest number of pieces needed to create the first word.


  • Words consist of characters in the ASCII range 33 to 126.
  • The word list may have repeats.
  • Construction of words is case sensitive (you can not use the piece "Head" as part of the word "forehead".)
  • Once you have used a piece in a construction, you can not use any part of that piece again (e.g if I use "lo" from "lone" as part of constructing "lolo", I cannot use "lo" from that "lone" again. However, if I had two "lone" in my word list, I could use one "lo" from each.)
  • Once you use a piece, you can still make pieces out of unused substrings in the word. (E.g. If I used "tt" in "butter", I still have "bu" and "er" left over to use. However, I can't combine them into one "buer" piece.)
  • If it is impossible to construct the input word using the word list given, output nothing, or something other than a positive integer.


(you only need to output the number)

  • "snack" ["food","Shoe","snack"] => 1 (snack)
  • "Snack" ["food","Shoe","snack"] => 2 (S + nack)
  • "frog" ["cat","dog","log"] => 0
  • "~~Frank~~" ["Frog~","~~Love","Hank~"] => 4 (~~ + Fr + ank~ + ~)
  • "loop-de-loop" ["loop", "frien-d","-elk","pool"] => 7 (loop + -d + e + - + l + oo + p)
  • "banana" ["can","can","boa"] => 4 (b+an+an+a)
  • "banana" ["can","boa"] => 0
  • "13frnd" ["fr13nd"] => 3 (13 + fr + nd)

Let me know if you think of more useful test cases.

  • 1
    \$\begingroup\$ pieces are usually called contiguous substrings. \$\endgroup\$
    – Mr. Xcoder
    Commented Jul 22, 2017 at 16:58
  • \$\begingroup\$ @Mr.Xcoder thanks, updated. \$\endgroup\$
    – geokavel
    Commented Jul 22, 2017 at 17:11

1 Answer 1


JavaScript, 209 206 bytes

f=(a,b,F)=>a?[...a].map((_,i)=>[...Array(i+1)].map((_,j)=>F||b.forEach((q,k)=>!F&&~(I=q.indexOf(a[S='substring'](j,r=a.length-i+j)))&&(F=b[k]=q[S](0,I)+' '+q[S](I+r+j),a=a[S](0,j)+a[S](r)))))&&F&&1+f(a,b):0

Try it online

Returns NaN if the combination is not found.


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.