Find a substring that splits into dictionary words

Given a string s and a dictionary of words, find a substring of s that splits, with nothing left over, into one or more dictionary words placed back to back. Words may repeat and may come in any order, and they can have different lengths. Return the start index of such a substring, or -1 if there is none.

Interface

Unless you agree on a different interface with the interviewer, assume:

• find_concatenation(s: str, words: list[str]) -> int — returns the smallest start index that works, or -1. Empty words are ignored.

Example

find_concatenation("xxxleetxx", ["leet"])               ->  3    # "leet" is one word
find_concatenation("applepenapple", ["apple", "pen"])   ->  0    # "applepen", or the whole string
find_concatenation("catsdog", ["dog", "cats", "sand"])  ->  0
find_concatenation("hello", ["world"])                  ->  -1

Constraints

• 0 <= len(s) <= 10^4; 0 <= len(words) <= 10^4; words have varying lengths.
• Words may be reused any number of times.

Clarifying questions

• Does a single word count as a concatenation of "one or more" words?
• If several start indexes work, which one should be returned?
• Must each word be used at most once, or exactly once? Are all words the same length?
• How large can the dictionary get, and can strings contain Unicode?

What a strong answer covers

• The word-break view: fix a start, and mark the positions reachable by jumping over dictionary words (DP or BFS), testing only the distinct word lengths with a hash set.
• The observation that settles it: since one word is already a valid concatenation, the smallest answer is the first index where any dictionary word starts. That turns the task into multi-pattern search: a trie walked from each position, or Aho-Corasick in O(len(s) + total word length + matches).
• Complexity of each approach and when the dictionary size makes the naive check too slow.
• Edge cases: empty string, empty dictionary, empty words, overlapping matches, Unicode normalization.

Follow-ups

• Return the longest substring that is such a concatenation.
• The classic version: all words have the same length and the substring must use every word exactly once. Return every start index, with a sliding window that moves one word length at a time and keeps word counts.
• The dictionary is huge and shared across many strings: what do you precompute?