String Matching in an Array (Substring Containment)
Given an array of strings, identify which words appear as substrings of any other word in the array (equivalently, find which words do NOT appear as substrings of any other word). With up to 100 unique lowercase strings of length ≤30, the core task is detecting pairwise substring containment. Optimize beyond the basic O(n^2 * L) brute force approach using techniques such as concatenation with separators and KMP/Z-algorithm, or trie-based methods.
Asked at:
Meta
Question Timeline
See when this question was last asked and where, including any notes left by other candidates.
Early November, 2025
Meta
Mid-level
You are given a codebase. You are given an array of strings words. Return all strings that are not a substring of any other string in words. eg. "cat", "category", "dog", "doggy" -> "category", "doggy" Basic interfaces and brute force solution ( O(n^2 * L) ) were provided. You were asked to write your own implementation and compare side-by-side. There were some tests and performance benchmarking they created.
Hello Interview Premium
Your account is free and you can post anonymously if you choose.