Academy
mediumJS ES6+#118

Palabrador (word overlapping)

Prompt

Given words, find the overlapping segment between the end of one word and the start of the next to form a new combined word. Example: ["abc","bcd","cde"] -> "abcde" (bc overlaps, cd overlaps). Words with no overlap just concatenate.

Solution

function overlapCombine(words) {
  if (words.length === 0) return ''
  return words.reduce((acc, word) => {
    let overlap = 0
    for (let i = 1; i <= Math.min(acc.length, word.length); i++) {
      if (acc.slice(-i) === word.slice(0, i)) overlap = i
    }
    return acc + word.slice(overlap)
  })
}
Mentor's take

This is suffix–prefix matching plus a fold: for each adjacent pair, find the longest suffix of the accumulated string that equals a prefix of the next word, then append only the non-overlapping remainder. reduce without an initial value seeds the fold with words[0] — exactly right here, but it throws on an empty array, hence the explicit guard.

The overlap search tries every candidate length i and compares acc.slice(-i) with word.slice(0, i), keeping the largest match. Note it must keep scanning to the max — taking the first match and breaking would return "a" overlap when "abc" overlap exists. Per pair that's O(m²) in the shorter length (m slice comparisons of length up to m), so the whole thing is roughly O(n·m²) — fine for words, and the honest answer when asked. The asymptotically better tool is the KMP failure function computed over word + '#' + acc, which finds the longest suffix-prefix overlap in O(m) — name it, don't code it, unless the interviewer pushes.

Also say the scope boundary: greedy pairwise merging is not the general shortest superstring problem (that one is NP-hard and order matters); this question fixes the order, which is what makes it tractable.

Red flag: breaking out of the loop on the first matching i — you want the longest overlap, so either scan all lengths keeping the max, or scan from the largest length downward and break. Off-by-one in slice(-i) vs slice(0, i) is the other classic; check i = full-word-length by hand.

Say it: "It's a fold with a suffix-prefix match per step — I keep the longest overlap, not the first, and I'd reach for KMP's failure function if the strings were long enough for O(m²) to matter."