How do I practice coding and algorithm questions?

Use PracHub's coding console to write, test, and debug your solutions in Python or JavaScript. View hints, test against sample inputs, and compare with official solutions.

What difficulty level is this coding question?

This is a Medium difficulty Coding & Algorithms question, commonly asked during Technical Screen rounds at Amazon.

What role is this question designed for?

This question is commonly asked for Software Engineer candidates at Amazon during technical interviews.

Find substring from dictionary concatenation

Quick Overview

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.

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.

Input: ("catsandog", ["cats", "dog", "sand", "and", "cat"])

Expected Output: 0

Explanation: "cat"+"sand" forms the substring s[0:7], so index 0 is valid even though the full string is not segmentable.

Input: ("xxxleetxx", ["leet"])

Expected Output: 3

Explanation: The only dictionary word "leet" appears at s[3:7]; no valid concatenation starts before index 3.

Input: ("hello", ["world"])

Expected Output: -1

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

Input: ("", ["a"])

Expected Output: -1

Explanation: Empty string contains no substring, so the answer is -1.

Input: ("aaa", ["a"])

Expected Output: 0

Explanation: "a" alone is a valid one-word concatenation starting at index 0 (words may be reused).

Input: ("bbaab", ["aa", "b"])

Expected Output: 0

Explanation: Even a single word "b" at index 0 is a valid concatenation of one word.

Input: ("zzab", ["ab"])

Expected Output: 2

Explanation: No word matches starting at indices 0 or 1; "ab" matches at s[2:4].

Input: ("abc", [])

Expected Output: -1

Explanation: An empty dictionary cannot form any concatenation, so the answer is -1.

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.

Quick Overview