Problem Description

You are given a list of phrases where each phrase is a string containing only lowercase English letters and spaces. Each phrase has no leading or trailing spaces and no consecutive spaces.

The task is to create "Before and After puzzles" by combining two phrases. A Before and After puzzle is formed when:

• The last word of one phrase matches the first word of another phrase
• The two phrases are merged by overlapping this common word

For example, if you have phrases "write code" and "code everyday", since "code" is the last word of the first phrase and the first word of the second phrase, you can create "write code everyday".

You need to:

1. Find all possible Before and After puzzles that can be formed from any two different phrases in the list (phrases at indices i and j where i != j)
2. Consider both orderings - phrase i followed by phrase j, and phrase j followed by phrase i
3. Return only distinct puzzles (remove duplicates)
4. Sort the result lexicographically (alphabetically)

The solution works by:

• First extracting the first and last words from each phrase
• Then checking all pairs of phrases to see if the last word of one matches the first word of another
• When a match is found, concatenating the phrases while removing the duplicate common word
• Finally, removing duplicates and sorting the results

Intuition

The key insight is that we only need to care about the first and last words of each phrase to determine if two phrases can form a Before and After puzzle. The middle words don't affect whether two phrases can be combined.

Think about it this way: if we want to check if phrase A can be followed by phrase B, we only need to verify if the last word of A equals the first word of B. Once we confirm this match, we can merge them by concatenating A with B (minus the overlapping word).

This leads us to a straightforward approach:

1. Preprocess each phrase to extract just the information we need - the first and last words. This avoids repeatedly splitting phrases during comparison.

2. Check all possible pairs systematically. Since we need to consider both orderings (A→B and B→A), we examine every pair (i, j) where i ≠ j.

3. Handle the concatenation carefully. When merging "write code" with "code everyday", we want "write code everyday", not "write code code everyday". So we concatenate the first phrase with the second phrase starting from after its first word: phrases[i] + phrases[j][len(first_word_of_j):].

4. Use a set to handle duplicates automatically. Different phrase pairs might produce the same puzzle, so storing results in a set eliminates duplicates efficiently.

5. Sort at the end rather than maintaining sorted order throughout, since we're collecting all results first anyway.

The beauty of this solution is its simplicity - by identifying that only the boundary words matter for matching, we reduce a potentially complex string manipulation problem to a simple comparison and concatenation task.

Learn more about Sorting patterns.

Solution Approach

The implementation follows a hash table and sorting strategy:

Step 1: Extract First and Last Words

ps = []
for p in phrases:
    ws = p.split()
    ps.append((ws[0], ws[-1]))

We iterate through each phrase and split it by spaces to get individual words. For each phrase, we store a tuple (first_word, last_word) in the array ps. This preprocessing step allows us to quickly access the boundary words without repeatedly splitting strings.

Step 2: Find All Valid Combinations

n = len(ps)
ans = []
for i in range(n):
    for j in range(n):
        if i != j and ps[i][1] == ps[j][0]:
            ans.append(phrases[i] + phrases[j][len(ps[j][0]):])

We use nested loops to check all possible pairs (i, j) where i ≠ j. For each pair:

• Check if the last word of phrase i (stored as ps[i][1]) equals the first word of phrase j (stored as ps[j][0])
• If they match, create the puzzle by concatenating:
  • The entire first phrase: phrases[i]
  • The second phrase starting after its first word: phrases[j][len(ps[j][0]):]

The slicing phrases[j][len(ps[j][0]):] skips the first word of the second phrase (including the space after it) to avoid duplication of the common word.

Step 3: Remove Duplicates and Sort

return sorted(set(ans))

Convert the list ans to a set to automatically remove any duplicate puzzles that might have been created from different phrase combinations. Then convert back to a sorted list for the final result.

Time Complexity: O(n² × m + k log k) where n is the number of phrases, m is the average length of phrases, and k is the number of unique puzzles generated.

Space Complexity: O(n + k) for storing the preprocessed word pairs and the resulting puzzles.

Example Walkthrough

Let's walk through a concrete example with the phrases: ["mission statement", "a quick bite to eat", "a chip off the old block", "chocolate bar", "mission impossible", "a man on a mission", "block party", "eat my words", "bar of soap"]

Step 1: Extract First and Last Words

We create tuples of (first_word, last_word) for each phrase:

• "mission statement" → ("mission", "statement")
• "a quick bite to eat" → ("a", "eat")
• "a chip off the old block" → ("a", "block")
• "chocolate bar" → ("chocolate", "bar")
• "mission impossible" → ("mission", "impossible")
• "a man on a mission" → ("a", "mission")
• "block party" → ("block", "party")
• "eat my words" → ("eat", "words")
• "bar of soap" → ("bar", "soap")

Step 2: Find All Valid Combinations

Now we check all pairs where the last word of one phrase matches the first word of another:

• Phrase 0 ("mission statement") has last word "statement" - no matches with any first words
• Phrase 1 ("a quick bite to eat") has last word "eat" - matches with phrase 7's first word "eat"
  • Creates: "a quick bite to eat" + "my words" = "a quick bite to eat my words"
• Phrase 2 ("a chip off the old block") has last word "block" - matches with phrase 6's first word "block"
  • Creates: "a chip off the old block" + "party" = "a chip off the old block party"
• Phrase 3 ("chocolate bar") has last word "bar" - matches with phrase 8's first word "bar"
  • Creates: "chocolate bar" + "of soap" = "chocolate bar of soap"
• Phrase 5 ("a man on a mission") has last word "mission" - matches with phrases 0 and 4's first word "mission"
  • Creates: "a man on a mission" + "statement" = "a man on a mission statement"
  • Creates: "a man on a mission" + "impossible" = "a man on a mission impossible"

Step 3: Remove Duplicates and Sort

We collected these puzzles:

• "a quick bite to eat my words"
• "a chip off the old block party"
• "chocolate bar of soap"
• "a man on a mission statement"
• "a man on a mission impossible"

Converting to a set (no duplicates in this case) and sorting lexicographically gives us the final result:

["a chip off the old block party",
 "a man on a mission impossible",
 "a man on a mission statement",
 "a quick bite to eat my words",
 "chocolate bar of soap"]

The key insight demonstrated here is how we only need to compare the boundary words (first and last) to determine if two phrases can be combined, and then we carefully concatenate them by skipping the duplicate common word.

Solution Implementation

Time and Space Complexity

Time Complexity: O(n^2 × m × (log n + log m))

The time complexity breaks down as follows:

• Initial parsing loop: O(n × m) where we split each phrase and extract first/last words
• Nested loops: O(n^2) iterations to check all pairs
• For each valid pair (when ps[i][1] == ps[j][0]):
  • String comparison: O(m) in worst case
  • String concatenation: O(m) to create phrases[i] + phrases[j][len(ps[j][0]):]
  • Note: len(ps[j][0]) is incorrect in the code - it should be counting characters in the first word, not the length of a tuple
• Converting to set: O(n^2 × m) in worst case if all pairs are valid
• Sorting the set: O(n^2 × log(n^2) × m) = O(n^2 × log n × m) for sorting potentially n^2 strings of average length m

The dominant operation is the sorting step combined with string operations, giving us O(n^2 × m × log n). However, considering string comparison during sorting adds another O(m) factor implicitly, and the reference answer includes log m which accounts for the complexity of comparing strings of length m during sorting operations.

Space Complexity: O(n^2 × m)

The space complexity consists of:

• ps list: O(n) for storing tuples of word references
• ans list: O(n^2 × m) in worst case if all pairs form valid puzzles, each of average length m
• set(ans): O(n^2 × m) for the set conversion
• Final sorted list: O(n^2 × m)

The dominant space usage is from storing the puzzle strings, giving us O(n^2 × m).

Learn more about how to find time and space complexity quickly.

Common Pitfalls

1. Incorrect Handling of Single-Word Phrases

A critical pitfall occurs when dealing with phrases that contain only a single word. In such cases, the phrase can match with itself if we're not careful about the implementation.

Problem Scenario: If the input contains ["a", "a"] (two identical single-word phrases), the algorithm might incorrectly produce "aa" by combining the same phrase at different indices.

Why This Happens:

• For single-word phrases, both the first and last word are the same
• When checking i != j, we correctly avoid using the same index twice
• However, with duplicate phrases at different indices, we can still create invalid combinations

Solution: The current implementation actually handles this correctly by checking i != j, which ensures we don't combine a phrase with itself at the same index. The issue only arises if there are duplicate phrases in the input, which is a valid scenario according to the problem.

2. Incorrect String Slicing for Overlap Removal

Problem Scenario: When removing the overlapping word from the second phrase, using phrases[j][len(phrase_boundaries[j][0]):] assumes there's always a space after the first word.

Why This Happens:

• For single-word phrases, there's no space after the word
• The slicing would start at the exact end of the phrase, returning an empty string
• This leads to correct behavior for single words but could be confusing

Better Approach:

# More explicit handling
if len(phrase_boundaries[j][0]) == len(phrases[j]):
    # Single word phrase - nothing to append after the overlap
    merged_puzzle = phrases[i]
else:
    # Multi-word phrase - skip first word and the space
    merged_puzzle = phrases[i] + phrases[j][len(phrase_boundaries[j][0]):]

3. Missing Space in Concatenation

Problem Scenario: The current slicing phrases[j][len(phrase_boundaries[j][0]):] doesn't include the space between the overlapping word and the rest of the second phrase.

Why This Happens:

• When we slice starting at len(first_word), we're not accounting for the space
• This could lead to puzzles like "write codeeveryday" instead of "write code everyday"

Solution: The code should slice from len(first_word) + 1 to skip both the word and the space:

# Skip the first word AND the space after it (if it exists)
if ' ' in phrases[j]:
    merged_puzzle = phrases[i] + ' ' + phrases[j][len(phrase_boundaries[j][0]) + 1:]
else:
    # Single word phrase
    merged_puzzle = phrases[i]

4. Memory Inefficiency with Large Duplicate Results

Problem Scenario: If many phrase combinations produce the same puzzle, we store all duplicates in memory before deduplication.

Why This Happens:

• The list puzzle_results stores all combinations before converting to a set
• With many phrases sharing common words, this could create numerous duplicates

Optimized Solution: Use a set from the beginning to avoid storing duplicates:

puzzle_results = set()  # Use set instead of list
for i in range(num_phrases):
    for j in range(num_phrases):
        if i != j and phrase_boundaries[i][1] == phrase_boundaries[j][0]:
            overlap_length = len(phrase_boundaries[j][0])
            merged_puzzle = phrases[i] + phrases[j][overlap_length:]
            puzzle_results.add(merged_puzzle)  # add() instead of append()

return sorted(puzzle_results)  # No need for set() conversion