Let's say you have a sentence like:

this is a very long sentence with several words of no significance

It contains only the 26 lowercase letters of the alphabet and spaces.

And you have a dictionary, where each word contains any number of the 26 lowercase letters and nothing else:


Then the output should contain, among others:

  • tHis is a vEry long seNtence with several words of no siGnificancE
  • tHis is a vEry long senteNce with several words of no siGnificancE
  • this is a veRy long sENTence with several wOrds of no significaNce

So, every line of the output is the original sentence, but if only the uppercase letters of a line are taken, they should form a dictionary word. The program should find all possible such lines.

  • \$\begingroup\$ I have attempted to paraphrase certain parts of the question so that somebody like me can read them easier; I hope I haven't failed; feel free to rollback my edit if I have. \$\endgroup\$ Apr 12, 2020 at 13:47
  • 10
    \$\begingroup\$ Is the dictionary necessary? This doesn't make the challenge more interesting than just having a sentence and a single word as input. \$\endgroup\$ Apr 12, 2020 at 13:56
  • \$\begingroup\$ Also, more test cases would be appreciated. \$\endgroup\$ Apr 12, 2020 at 13:58
  • \$\begingroup\$ Might want to add something about the dictionary word being formed in or out of sequence. I assume you meant in sequence but it's not stated. \$\endgroup\$
    – Noodle9
    Apr 12, 2020 at 14:08
  • 1
    \$\begingroup\$ May I assume there are at least one sentence output for each word in the dictionary? If not so, I would suggest adding another testcase. \$\endgroup\$
    – tsh
    Jul 20, 2020 at 8:26

3 Answers 3


JavaScript, 474 bytes

k=((e,r)=>{for(o=[],e=[...e],r=[...r],w=r.reduce((r,h,n)=>!(r[n]=e.map((e,r)=>h==e?r:"").filter(Number))||r,[]),[z]=w,h=[],x=0;x<w.reduce((e,r)=>e*=r.length||e,1);x++)z.forEach((e,r)=>{for(g=[z[r]],j=1;j<w.length;j++)for(n=w[j],y=0;y<n.length;y++)if(g.slice(-1)[0]<n[y]&&!h.some(e=>e.toString()==[...g,n[y]].toString())){g.push(n[y]);break}h.push(g)});return h.filter(e=>e.length==w.length).forEach(r=>{d=[...e],r.forEach(e=>d[e]=d[e].toUpperCase()),o.push(d.join(""))}),o})

Live example:

k=((e,r)=>{for(o=[],e=[...e],r=[...r],w=r.reduce((r,h,n)=>!(r[n]=e.map((e,r)=>h==e?r:"").filter(Number))||r,[]),[z]=w,h=[],x=0;x<w.reduce((e,r)=>e*=r.length||e,1);x++)z.forEach((e,r)=>{for(g=[z[r]],j=1;j<w.length;j++)for(n=w[j],y=0;y<n.length;y++)if(g.slice(-1)[0]<n[y]&&!h.some(e=>e.toString()==[...g,n[y]].toString())){g.push(n[y]);break}h.push(g)});return h.filter(e=>e.length==w.length).forEach(r=>{d=[...e],r.forEach(e=>d[e]=d[e].toUpperCase()),o.push(d.join(""))}),o})

console.log(k('this is a very long sentence with several words of no significance', 'henge'));


For each letter in the word, an array of indices is constructed corresponding to every position of that letter in the sentence.

Then inside a nest of 4 for loops, every possible path from the first array to the last array is computed, where each step is into an element with greater numeric value in the next array.

This produces an array of paths whose length is equal to the maximum possible paths, which is the product of multiplying the length of each letter indices array (this number gets big real quick as the length of the word increases).

Then all paths whose length is smaller than the word are excluded, since they failed to find a valid step between each array.

You can see the unminified logic at this stackoverflow answer.

I am confused by this line (even though it's my code), whose intent is to check the existing paths before adding a step to the current path to make sure its constructing a unique path:

if (!paths.some(p => p.toString() == [...path, arrays[j][y]].toString())) {

It seems to me like this should erroneously prevent construction of multiple paths who share any beginning steps. But it actually works as intended. So I am stumped.


Python 3, 169 bytes

a=lambda c,w:(([c[0]+k for k in a(c[1:],w)]+([c[0].upper()+k for k in a(c[1:],w[1:])]if c[0]==w[0]else[]))if c else[])if w else[c]
lambda c,d:sum((a(c,w)for w in d),[])

Takes as input the sentence as a string and the dictionary as a list of strings. Uses a recursive helper function a(c,w) to compute the output for each word in the dictionary at a time, then sums the lists together to get the final output. The helper function works through the sentence/word one character at a time, and has several cases:

  1. No more characters in the word, return what's left of the sentence

  2. No more characters in the sentence, return empty list

  3. Characters left in both, return same results as a(c[1:],w), with c[0] prepended to each result.

  4. Characters left in both, and beginning characters match, return (3.) in addition to a(c[1:],w[1:]), with c[0].upper() prepended to each result.

There's definitely a few bytes of savings to be had in the helper method; I wasn't being super careful with my parentheses around the inline if-expressions (and the precedence is slightly confusing) -- I might take a closer look tomorrow to see if I can shave off a few bytes.


Perl 5 -pF, 96 bytes

Takes the sentence as the first input and all subsequent inputs are treated as the dictionary. Could produce the strings in the reverse order for +1 byte. I still feel there's room to golf this...

$"=").*(";m#(@{[<>=~/./g]})(?{$a=%h=();$h{$_}++for@-;map$\.=$h{$a++}?uc:lc,@F})(?!)# while!eof}{

Try it online!


This script uses Perl's regex engine to perform the matching.

First $" is set to ).*(, this is the separator that's used when lists are interpolated. A m//atch is then started (with # as the delimiter) which contains the current input dictionary word (<>), interpolated (@{[...]}) into the match as as a list (=~/./g). Example.

The next part of the m// operation is a zero-length code block. In here there is access to all the magic variables associated with regex ($&, $1, etc). $a and %h are initialised as empty (() - technically $a is set to the length, which is 0) and @-, which contains the start of each matched group, is used to populate the indices of %h with 1 (++) for the position of all the matches.

Finally, @F (which is automatically filled with the chars from the input via -F) is looped over while there's still input (!eof), checking %h's key $a (incremented for each char in @F) to see if it's truthy (1) or not (undef for missing key). If it's truthy uc returns (its operand, or $_ if none passed, which is set for each item in @F via map{...}@F) the item uppercased, otherwise lc returns it lowercased. This is appended to $\ which is implicitly output after anything is printed, which because -p is specified, will happen after the (implicit - from -p) input loop exits. Due to this, it's also necessary to break out of the surrounding loops with }{ so that we don't get an unmodified copy of the input printed too.


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.