LeetCode 1181 - Before and After Puzzle

LeetCode Problem 1181

Difficulty: 🟡 Medium
Topics: Array, Hash Table, String, Sorting

Solution

Problem Understanding

The problem gives us an array of phrases, where each phrase is a string made of lowercase English letters and spaces. Every phrase is well-formed, meaning there are no leading or trailing spaces and no consecutive spaces.

We must generate all possible "Before and After" puzzles by combining two different phrases. A valid merge happens when the last word of the first phrase is exactly the same as the first word of the second phrase.

Suppose we have:

"writing code"
"code rocks"

The last word of the first phrase is "code" and the first word of the second phrase is also "code". Since they match, we merge them into:

"writing code rocks"

The overlapping word appears only once in the final result.

The order matters. If phrase A can merge into phrase B, that does not automatically mean B can merge into A. We must consider every ordered pair (i, j) where i != j.

The final answer must satisfy two additional requirements:

• All generated puzzles must be distinct
• The output must be sorted lexicographically

The constraints are relatively small:

• At most 100 phrases
• Each phrase length is at most 100 characters

These limits tell us that an O(n^2) comparison approach is completely acceptable because 100^2 = 10,000, which is small.

Several edge cases are important:

• Multiple identical phrases may exist
• Different phrase pairs may generate the same merged result
• Single-word phrases are allowed
• A phrase can only merge with another phrase at a different index, even if the text is identical
• Some phrases may participate in many merges
• Some phrases may not participate in any merge at all

A naive implementation can easily produce duplicates or incorrectly duplicate the overlapping word during concatenation.

Approaches

Brute Force Approach

The brute-force solution examines every ordered pair of phrases (i, j) where i != j.

For each pair:

1. Extract the last word of phrases[i]
2. Extract the first word of phrases[j]
3. Compare them
4. If they match, construct the merged phrase
5. Insert the merged phrase into a set to remove duplicates

After processing all pairs, convert the set into a sorted list.

This approach is correct because it explicitly checks every possible valid pairing. Since the problem requires considering all ordered pairs, exhaustive checking guarantees no valid merge is missed.

The downside is that we repeatedly split phrases and repeatedly compare many pairs that have no chance of matching.

Key Insight for an Improved Solution

The important observation is that phrases only matter if:

• Their last word matches another phrase's first word

Instead of blindly comparing every pair, we can group phrases by their first word.

We build a hash map:

first_word -> list of phrase indices

Then, for each phrase:

1. Extract its last word
2. Look up all phrases whose first word matches that last word
3. Generate merges only for those candidates

This avoids unnecessary comparisons and makes the logic cleaner and more scalable.

Even though the asymptotic complexity remains close to O(n^2) in the worst case, the hash map significantly reduces wasted work in practice.

Approach Comparison

Approach	Time Complexity	Space Complexity	Notes
Brute Force	O(n² * L)	O(k)	Checks every pair directly
Optimal	O(n² * L) worst case	O(n + k)	Uses hash map to only examine relevant matches

Here:

• n is the number of phrases
• L is the average phrase length
• k is the number of generated distinct puzzles

Algorithm Walkthrough

1. Create a hash map that groups phrase indices by their first word.

For every phrase, split it into words and extract the first word. Store the phrase index inside:

first_word_map[first_word]

This allows fast lookup of all phrases that can potentially follow another phrase. 2. Create an empty set to store generated puzzles.

A set automatically removes duplicates, which is required because different phrase pairs may produce the same merged result. 3. Iterate through every phrase as the first phrase.

For each phrase:

• Split it into words
• Extract the last word

4. Use the last word to look up candidate second phrases.

If the last word exists in the hash map, then all phrases associated with that word are potential matches. 5. For every candidate second phrase:

• Skip the case where indices are equal because i != j
• Merge the phrases carefully

Suppose:

phrase1 = "writing code"
phrase2 = "code rocks"

We do not want:

"writing code code rocks"

Instead, we remove the duplicated first word from the second phrase and append only the remaining suffix. 6. Insert the merged phrase into the result set. 7. After all phrases are processed:

• Convert the set into a list
• Sort lexicographically
• Return the sorted list

Why it works

The algorithm works because every valid puzzle must satisfy exactly one condition:

last_word(phrase1) == first_word(phrase2)

The hash map guarantees we efficiently find every phrase that satisfies this condition. Since every valid ordered pair is considered exactly once, no valid puzzle is missed. Using a set guarantees duplicates are removed. Finally, sorting produces the required lexicographical order.

Python Solution

from typing import List
from collections import defaultdict

class Solution:
    def beforeAndAfterPuzzles(self, phrases: List[str]) -> List[str]:
        first_word_map = defaultdict(list)

        # Map first word -> indices of phrases
        for index, phrase in enumerate(phrases):
            words = phrase.split()
            first_word = words[0]
            first_word_map[first_word].append(index)

        results = set()

        # Try every phrase as the first phrase
        for i, phrase1 in enumerate(phrases):
            words1 = phrase1.split()
            last_word = words1[-1]

            # Find phrases whose first word matches
            for j in first_word_map.get(last_word, []):
                if i == j:
                    continue

                phrase2 = phrases[j]
                words2 = phrase2.split()

                # Merge while avoiding duplicate overlap word
                merged = phrase1 + phrase2[len(words2[0]):]

                results.add(merged)

        return sorted(results)

The implementation begins by constructing a hash map that groups phrase indices according to their first word. This preprocessing step enables efficient lookup later.

The main loop treats each phrase as the potential first phrase in a merge. For every phrase, we extract its last word and use the hash map to find candidate second phrases whose first word matches.

The merge operation is subtle. Instead of reconstructing the second phrase manually from split words, we reuse string slicing:

phrase2[len(words2[0]):]

This removes the overlapping first word from the second phrase while preserving the leading space before the remaining words.

For example:

phrase2 = "code rocks"
words2[0] = "code"
phrase2[4:] = " rocks"

Appending this suffix directly creates the correct merged result.

The set ensures uniqueness, and the final sorted conversion satisfies the lexicographical ordering requirement.

Go Solution

package main

import (
	"sort"
	"strings"
)

func beforeAndAfterPuzzles(phrases []string) []string {
	firstWordMap := make(map[string][]int)

	// Map first word -> indices
	for i, phrase := range phrases {
		words := strings.Split(phrase, " ")
		firstWord := words[0]
		firstWordMap[firstWord] = append(firstWordMap[firstWord], i)
	}

	results := make(map[string]bool)

	// Try every phrase as the first phrase
	for i, phrase1 := range phrases {
		words1 := strings.Split(phrase1, " ")
		lastWord := words1[len(words1)-1]

		candidates, exists := firstWordMap[lastWord]
		if !exists {
			continue
		}

		for _, j := range candidates {
			if i == j {
				continue
			}

			phrase2 := phrases[j]
			words2 := strings.Split(phrase2, " ")

			merged := phrase1 + phrase2[len(words2[0]):]
			results[merged] = true
		}
	}

	answer := make([]string, 0, len(results))

	for phrase := range results {
		answer = append(answer, phrase)
	}

	sort.Strings(answer)

	return answer
}

The Go solution follows the same algorithmic structure as the Python implementation.

A map[string][]int is used for the first-word lookup table. Since Go does not have a built-in set type, uniqueness is implemented using:

map[string]bool

String slicing works similarly to Python because Go strings are byte slices. Since the problem guarantees lowercase English letters and spaces only, byte indexing is safe and there are no Unicode concerns.

The final results are collected into a slice and sorted using sort.Strings.

Worked Examples

Example 1

Input:

["writing code", "code rocks"]

Step 1: Build first-word map

Phrase	First Word
writing code	writing
code rocks	code

Map becomes:

Key	Value
writing	[0]
code	[1]

Step 2: Process each phrase

Phrase 0: "writing code"

Last word:

code

Lookup:

firstWordMap["code"] = [1]

Candidate:

"code rocks"

Merge:

"writing code" + " rocks"
= "writing code rocks"

Result set:

{"writing code rocks"}

Phrase 1: "code rocks"

Last word:

rocks

No matching first word exists.

Final sorted output:

["writing code rocks"]

Example 2

Input:

[
    "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"
]

First-word map

First Word	Indices
mission	[0, 4]
a	[1, 2, 5]
chocolate	[3]
block	[6]
eat	[7]
bar	[8]

Important merges

First Phrase	Last Word	Matching Phrase	Result
a chip off the old block	block	block party	a chip off the old block party
a man on a mission	mission	mission impossible	a man on a mission impossible
a man on a mission	mission	mission statement	a man on a mission statement
a quick bite to eat	eat	eat my words	a quick bite to eat my words
chocolate bar	bar	bar of soap	chocolate bar of soap

Sorted 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"
]

Example 3

Input:

["a", "b", "a"]

Processing

Pair (0, 2):

"a" + ""
= "a"

Pair (2, 0):

"a" + ""
= "a"

The set removes duplicates.

Final output:

["a"]

Example 4

Input:

["ab ba", "ba ab", "ab ba"]

Valid merges

Pair	Result
(0,1)	ab ba ab
(1,0)	ba ab ba
(1,2)	ba ab ba
(2,1)	ab ba ab

Set removes duplicates.

Final output:

["ab ba ab", "ba ab ba"]

Complexity Analysis

Measure	Complexity	Explanation
Time	O(n² * L) worst case	In the worst case many phrases share the same first/last word
Space	O(n + k)	Hash map plus distinct generated results

Here:

• n is the number of phrases
• L is the average phrase length
• k is the number of distinct generated puzzles

The preprocessing map requires linear space relative to the number of phrases. The dominant cost comes from generating and storing merged strings. Although the hash map reduces unnecessary comparisons in practice, the worst case still approaches quadratic behavior if every phrase can connect to every other phrase.

Test Cases

sol = Solution()

# Example 1
assert sol.beforeAndAfterPuzzles(
    ["writing code", "code rocks"]
) == ["writing code rocks"]  # simple merge

# Example 2
assert sol.beforeAndAfterPuzzles(
    [
        "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"
    ]
) == [
    "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"
]  # multiple valid merges

# Example 3
assert sol.beforeAndAfterPuzzles(
    ["a", "b", "a"]
) == ["a"]  # duplicate merged result

# Example 4
assert sol.beforeAndAfterPuzzles(
    ["ab ba", "ba ab", "ab ba"]
) == ["ab ba ab", "ba ab ba"]  # repeated phrases

# No valid merges
assert sol.beforeAndAfterPuzzles(
    ["hello world", "python code"]
) == []  # no matching boundaries

# Single phrase
assert sol.beforeAndAfterPuzzles(
    ["alone"]
) == []  # cannot merge with itself

# Chain-style overlaps
assert sol.beforeAndAfterPuzzles(
    ["a b", "b c", "c d"]
) == ["a b c", "b c d"]  # sequential merges

# Multiple duplicates
assert sol.beforeAndAfterPuzzles(
    ["x y", "y z", "x y"]
) == ["x y z"]  # same result from multiple pairs

# Single-word phrases
assert sol.beforeAndAfterPuzzles(
    ["a", "a"]
) == ["a"]  # overlap consumes entire second phrase

# Multiple possible matches
assert sol.beforeAndAfterPuzzles(
    ["start end", "end middle", "end finish"]
) == [
    "start end finish",
    "start end middle"
]  # one phrase connects to multiple others

Test Summary

Test	Why
["writing code", "code rocks"]	Basic valid merge
Large mixed example	Multiple independent merges
["a", "b", "a"]	Duplicate output handling
["ab ba", "ba ab", "ab ba"]	Repeated phrases and duplicates
No valid merges	Ensures empty output works
Single phrase	Cannot merge with itself
Sequential overlaps	Multiple chain-like connections
Multiple duplicates	Same result from different pairs
Single-word phrases	Entire phrase overlap
One-to-many matches	One phrase matching multiple candidates

Edge Cases

One important edge case occurs when multiple phrase pairs generate the same merged phrase. For example:

["a", "a"]

Both (0,1) and (1,0) generate "a". A naive implementation using a list would produce duplicates in the final answer. This implementation uses a set, which guarantees uniqueness automatically.

Another important edge case involves single-word phrases. Consider:

["a", "a"]

When merging, the overlapping word completely consumes the second phrase. If string concatenation is implemented incorrectly, extra spaces or duplicated words can appear. The slicing approach correctly appends an empty suffix and produces "a".

A third tricky case involves repeated phrases with different indices:

["ab ba", "ba ab", "ab ba"]

Even though the phrase text repeats, indices are still distinct. The problem only forbids i == j, not identical content. The implementation correctly allows merges between different indices while preventing self-merges.

A final edge case occurs when no valid matches exist at all. In such cases, the algorithm should return an empty list rather than None or an unsorted structure. Since the result set simply remains empty, converting and sorting it naturally returns an empty list.