Domain 2MediumMEDIUM

Before and After Puzzle

Identify pairs of phrases where the last word of one matches the first word of another, merge them by removing duplicate boundary words using a set for uniqueness, and return unique sorted results.

Domain: medium•Updated: 2026-09-10
#brute force#set#O(N^2)#sorting

Problem Breakdown

The problem requires generating “Before and After” puzzles from two phrases. A valid puzzle is formed when the last word of phrase i matches the first word of phrase j. The merging process involves concatenating them while ensuring the common boundary word appears only once (dropping it from the end of the first phrase). We must consider all pairs (i,j)(i, j) where i≠ji \neq j. Finally, we return a list of distinct strings sorted lexicographically.

Intuition

Given the constraint phrases.length <= 100, an O(N2)O(N^2) brute-force approach is computationally feasible (1002=10,000100^2 = 10,000 operations). We can iterate through every pair to check for boundary matches. To handle the requirement of returning distinct strings efficiently without duplicates during construction, a Python set is ideal because it automatically handles uniqueness and allows O(1)O(1) average time complexity lookups/insertions (though insertion here happens only on match). Sorting at the very end ensures lexicographical order as required.

Approach

  1. Pre-processing: To optimize efficiency within the nested loops, split all phrases into lists of words upfront before entering the pair iteration logic. This avoids redundant string splitting operations inside the inner loop.
  2. Pair Iteration: Iterate through every phrase index i (outer loop) and every phrase index j (inner loop).
  3. Boundary Check: For each pair, check if the last word of phrases[i] matches the first word of phrases[j]. Skip pairs where i==ji == j.
  4. Merge Construction: If a match is found:
    • Take all words from phrase i except the last one ([:-1]).
    • Append all words from phrase j (including its first word).
    • Join these combined words with spaces to form the puzzle string.
  5. Storage and Return: Add each valid puzzle string to a set. After checking all pairs, convert the set to a list and sort it lexicographically before returning.

Complexity Analysis

  • Time: O(N2⋅L)O(N^2 \cdot L), where NN is the number of phrases and LL is the maximum length of a phrase (for word splitting/joining). The dominant factor is checking all pairs (N2N^2), with string operations proportional to phrase length. Sorting takes O(Klog⁡K)O(K \log K) where KK is the number of unique results, which is negligible compared to pair generation for small inputs but included in worst-case analysis.
  • Space: O(N⋅L+K⋅L)O(N \cdot L + K \cdot L). We store pre-split words (N⋅LN \cdot L), plus the set of resulting puzzles (K⋅LK \cdot L).

Solution

from typing import List, Set

class Solution:
    def beforeAndAfterPuzzles(self, phrases: List[str]) -> List[str]:
        # Pre-process all phrases into word lists to avoid repeated splitting in loops
        phrase_words = [p.split() for p in phrases]
        
        result_set: Set[str] = set()
        n = len(phrases)
        
        for i in range(n):
            last_word_i = phrase_words[i][-1]
            
            # Optimization: Cache the words list of j to avoid repeated access overhead? 
            # Actually, accessing list is O(1). Splitting was removed.
            for j in range(n):
                if i == j:
                    continue
                
                first_word_j = phrase_words[j][0]
                
                # Check boundary condition: last word of i vs first word of j
                if last_word_i == first_word_j:
                    
                    # Construct the merged puzzle. 
                    # We drop the last word from 'i' (the common one) and keep all words in 'j'.
                    combined_words = phrase_words[i][:-1] + phrase_words[j]
                    
                    result_set.add(' '.join(combined_words))
        
        return sorted(list(result_set))

Edge Cases Handled

  • No Matches: If no pairs satisfy the condition, result_set remains empty; returns an empty list.
  • Identical Phrases at Different Indices: Example 3 (["a", "b", "a"]) correctly treats indices as distinct entities (i=0i=0 vs j=2j=2), allowing a match on content even if strings are identical, while preventing self-matching via the if i == j: continue check.
  • Single Word Phrases: Logic holds (e.g., dropping last word from single-word phrase results in empty list before appending second phrase).
  • Duplicate Results: The use of a Python set ensures that if multiple pairs generate the exact same puzzle string, only one instance is kept in the final output.