Find a String Containing Another
Company: Meta
Role: Machine Learning Engineer
Category: Coding & Algorithms
Difficulty: medium
Interview Round: Technical Screen
Given a list of strings, determine whether any string in the list contains another string from the same list as a contiguous substring.
Return one string that contains at least one other distinct string from the list. If multiple strings qualify, return any one of them. If no such string exists, return an empty string.
Example:
```text
Input: ["programming", "am", "pro"]
Output: "programming"
```
Explanation: `"programming"` contains both `"am"` and `"pro"` as substrings.
Implement the function and explain its time and space complexity. Also discuss two or three approaches that improve on a naive brute-force comparison of every pair of strings.
Quick Answer: This question evaluates proficiency in string algorithms, substring search techniques, and algorithmic complexity analysis within the Coding & Algorithms domain.
Given a list of strings, return one string that contains at least one other distinct string from the same list as a contiguous substring. If multiple strings qualify, you may return any one of them. If no such string exists, return an empty string.
A string does not count as containing itself. Also, duplicate copies of the exact same text do not create a valid match by themselves; the contained string must be a different string value.
Example:
Input: ["programming", "am", "pro"]
Output: "programming"
Explanation: "programming" contains both "am" and "pro" as substrings.
After implementing the function, explain its time and space complexity. As a follow-up, discuss two or three approaches that improve on the naive strategy of comparing every pair of strings independently.
Constraints
- 1 <= len(strings) <= 10^4
- 1 <= len(strings[i]) <= 10^3
- The sum of all string lengths is at most 2 * 10^5
- Strings are case-sensitive and duplicate values may appear
Examples
Input: (["programming", "am", "pro"],)
Expected Output: "programming"
Explanation: "programming" contains both "am" and "pro", and no other string in the list contains a different string.
Input: (["cat", "dog", "bird"],)
Expected Output: ""
Explanation: No string contains any other distinct string as a contiguous substring.
Hints
- Checking every pair of strings separately repeats a lot of work. Can you preprocess all words into one shared search structure?
- A trie with failure links (Aho-Corasick) lets you scan each word once while simultaneously checking for every other word as a substring.