Longest Word Containing Another Input

Given an array of nonempty lowercase English strings words, find an input string that contains at least one other input string as a contiguous substring.

An input at index i qualifies when some index j != i satisfies that words[j] occurs in words[i]. Equal strings at different indices count as a match; a string does not match itself at the same index.

Return the longest qualifying string. If several qualifying strings have the same length, return the one appearing first in the input array. Return the empty string "" when none qualifies. Matching is literal and case-sensitive.

Optimization discussion

A direct baseline checks every ordered pair and compares characters at every possible substring start. Explain its time and space cost, then describe two faster approaches and implement one. Length-based pruning and multi-pattern search are useful directions.

Only the returned string is graded; the complexity discussion is interview practice.