Find substring from dictionary concatenation
Company: Amazon
Role: Software Engineer
Category: Coding & Algorithms
Difficulty: medium
Interview Round: Technical Screen
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.
Quick Answer: This question evaluates proficiency in string-processing algorithms, word-lookup data structures and algorithmic complexity analysis within the Coding & Algorithms domain. It is commonly asked to assess practical implementation ability and conceptual understanding of performance trade-offs, edge-case handling (e.g.
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.
Examples
Input: ("leetcode", ["leet", "code"])
Expected Output: 0
Explanation: "leet"+"code" spans the whole string starting at index 0.
Input: ("applepenapple", ["apple", "pen"])
Expected Output: 0
Explanation: From index 0, "apple"+"pen" (and the full string) is a valid concatenation.
Hints
- 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?
- 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.
- 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.
- 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.