Concatenated Words

Concatenated Words

What is this problem about?

The Concatenated Words interview question asks you to find all strings in a given list that are "concatenated words." A concatenated word is defined as a string that can be entirely formed by joining at least two other shorter words from the same list.

Why is this asked in interviews?

Companies like Salesforce, Amazon, and Apple use the Dynamic Programming interview pattern to test your string decomposition skills. It’s a variation of the "Word Break" problem but applied to an entire set. It evaluates if you can optimize the search by sorting words by length or using a Trie/HashSet to speed up the sub-word lookups.

Algorithmic pattern used

The most common approach is DFS with Memoization or Word Break DP.

1. Store all words in a HashSet for O(1) lookup.
2. Sort words by length (optional, but helps process shorter words first).
3. For each word, check if it can be split into two or more words from the set.
4. The "can split" check is a standard DP: dp[i] is true if the prefix of length i can be formed by words in the set.

Example explanation

Words: ["cat", "cats", "dog", "catsdogcats"]

1. "cat": Cannot be split into shorter words.
2. "cats": Cannot be split.
3. "dog": Cannot be split.
4. "catsdogcats":
   • Can we split at "cats"? Yes, "cats" is in the set.
   • Remaining: "dogcats".
   • Can we split "dogcats" at "dog"? Yes.
   • Remaining: "cats".
   • Is "cats" in the set? Yes. Result: "catsdogcats".

Common mistakes candidates make

• Recursive Overlap: Not using memoization, leading to redundant checks for the same suffix.
• Including the word itself: Accidentally concluding that a word is a "concatenated word" because it matches itself in the set. You must ensure at least two distinct segments are found.
• Inefficient Set: Using a list for lookups instead of a HashSet or Trie.

Interview preparation tip

Mention that you can use a Trie to further optimize the prefix searching. This is particularly useful if the words share many common prefixes.