Find substring from dictionary concatenation

Given a string s and a dictionary of words dict, determine whether s contains a substring that is exactly a concatenation of one or more words from dict (words may be reused; order is arbitrary). Return the start index of any one such substring, or -1 if none exists. Words can have varying lengths. Discuss an efficient algorithm, its time and space complexity, and edge cases (e.g., overlapping matches, very large dict, unicode). Implement a function solve(s: string, dict: List[str]) -> int.

Find substring from dictionary concatenation

Given a string s and a dictionary of words dict, determine whether s contains a substring that is exactly a concatenation of one or more words from dict. Words may be reused, and the order in which they appear is arbitrary. Return the start index of any one such substring, or -1 if none exists.

A "concatenation" means the substring can be split, with no leftover characters, into a sequence of one or more dictionary words placed back-to-back. Words can have varying lengths.

Implement solve(s, dict) returning the start index (0-based) of any valid substring, or -1.

Example 1:

Input: s = "xxxleetxx", dict = ["leet"]
Output: 3

Explanation: s[3:7] = "leet" is exactly one dictionary word.

Example 2:

Input: s = "applepenapple", dict = ["apple", "pen"]
Output: 0

Explanation: Starting at index 0, "apple"+"pen" forms "applepen" (and the full "applepenapple" also works); index 0 is reported.

Example 3:

Input: s = "hello", dict = ["world"]
Output: -1

Explanation: No substring of s is a concatenation of dictionary words.

Constraints

• 0 <= len(s) <= 10^4
• 0 <= len(dict) <= 10^4
• Each word in dict consists of printable characters; words may have varying lengths.
• Words may be reused any number of times, in any order.
• Return the start index of any valid concatenation substring; if multiple start indices work, the smallest is acceptable.

Hints

1. A substring being a concatenation of dictionary words is exactly the classic word-break condition applied to that substring. Anchor a start index and ask: can I reach some later position using only dictionary-word jumps?
2. Fix a start index i, then do a DP/BFS over positions: a position j is reachable if it equals i or some reachable earlier position p has s[p:j] in the dictionary. The first i from which any position beyond i is reachable is your answer.
3. Precompute the set of distinct word lengths so that from each reachable position you only test those lengths instead of every possible substring. Use a hash set for O(L) membership checks.
4. Edge cases: empty s or empty dict return -1; a single word match counts as a valid concatenation (one or more words); make sure end > i so a zero-length 'match' never counts.