Before and After Puzzle - Practice Coding Problems

Before and After Puzzle - Problem

Given a list of phrases, generate a list of Before and After puzzles.

A phrase is a string that consists of lowercase English letters and spaces only. No space appears in the start or the end of a phrase. There are no consecutive spaces in a phrase.

Before and After puzzles are phrases that are formed by merging two phrases where the last word of the first phrase is the same as the first word of the second phrase. Note that only the last word of the first phrase and the first word of the second phrase are merged in this process.

Return the Before and After puzzles that can be formed by every two phrases phrases[i] and phrases[j] where i != j. Note that the order of matching two phrases matters, we want to consider both orders.

You should return a list of distinct strings sorted lexicographically, after removing all duplicate phrases in the generated Before and After puzzles.

Input & Output

Example 1 — Basic Connection

$ Input: phrases = ["writing code", "code review"]

› Output: ["writing code review"]

💡 Note: The last word "code" of first phrase matches the first word "code" of second phrase. Merge by removing the duplicate: "writing code" + "review" = "writing code review"

Example 2 — Multiple Connections

$ Input: phrases = ["mission statement", "a quick", "quick brown", "brown fox", "fox jumps"]

› Output: ["a quick brown fox", "a quick brown fox jumps", "quick brown fox jumps"]

💡 Note: Multiple chains possible: "a quick" → "quick brown" → "brown fox" → "fox jumps" creates several valid before-and-after puzzles

Example 3 — No Connections

$ Input: phrases = ["hello world", "good morning", "nice day"]

› Output: []

💡 Note: No phrase's last word matches any other phrase's first word, so no before-and-after puzzles can be formed

Constraints

1 ≤ phrases.length ≤ 100
1 ≤ phrases[i].length ≤ 100
phrases[i] consists of lowercase English letters and spaces
No phrase has leading or trailing spaces
No phrase has consecutive spaces

Visualization

Tap to expand

Understanding the Visualization

Input Phrases

Array of phrases with first and last words

Find Connections

Match last word of one phrase with first word of another

Merge Phrases

Combine phrases by removing duplicate connecting word

Key Takeaway

🎯 Key Insight: Use hash maps to efficiently match last words with first words instead of checking every pair

Asked in

G Google 15 a Amazon 12 M Microsoft 8

The key insight is to recognize that we need to match last words with first words efficiently. The best approach uses hash maps to group phrases by their first and last words, enabling O(1) lookups instead of O(n²) comparisons. Time: O(n×m + k×m), Space: O(n×m) where n is phrases count, m is average phrase length, and k is result count.

Common Approaches

Approach	Time	Space	Notes
✓ Brute Force	O(n² × m)	O(k × m)	Check every pair of phrases to see if they can form a before-and-after puzzle
Hash Map Optimization	O(n × m + k × m)	O(n × m)	Use hash maps to group phrases by first and last words for efficient matching

Brute Force — Algorithm Steps

Extract first and last words from each phrase
Compare every phrase pair (i,j) where i≠j
If last word of phrase i equals first word of phrase j, merge them
Remove duplicates and sort results

Visualization

Tap to expand

Step-by-Step Walkthrough

Split Words

Break each phrase into individual words

Compare Pairs

Check if last word of first matches first word of second

Merge

Combine phrases by removing duplicate connecting word

Code -

solution.c — C

#include <stdio.h>
#include <stdlib.h>
#include <string.h>

#define MAX_PHRASES 1000
#define MAX_LEN 1000
#define MAX_WORDS 100

char results[MAX_PHRASES * MAX_PHRASES][MAX_LEN];
int resultCount = 0;

int compare(const void *a, const void *b) {
    return strcmp((char*)a, (char*)b);
}

char** solution(char phrases[][MAX_LEN], int phrasesSize, int* returnSize) {
    resultCount = 0;
    
    for (int i = 0; i < phrasesSize; i++) {
        for (int j = 0; j < phrasesSize; j++) {
            if (i != j) {
                char words1[MAX_WORDS][MAX_LEN], words2[MAX_WORDS][MAX_LEN];
                int count1 = 0, count2 = 0;
                
                // Split first phrase into words
                char *token = strtok(phrases[i], " ");
                while (token != NULL && count1 < MAX_WORDS) {
                    strcpy(words1[count1++], token);
                    token = strtok(NULL, " ");
                }
                
                // Split second phrase into words
                char temp[MAX_LEN];
                strcpy(temp, phrases[j]);
                token = strtok(temp, " ");
                while (token != NULL && count2 < MAX_WORDS) {
                    strcpy(words2[count2++], token);
                    token = strtok(NULL, " ");
                }
                
                // Check if last word of first equals first word of second
                if (count1 > 0 && count2 > 0 && strcmp(words1[count1-1], words2[0]) == 0) {
                    char merged[MAX_LEN] = "";
                    
                    // Add all words from first phrase
                    for (int k = 0; k < count1; k++) {
                        if (k > 0) strcat(merged, " ");
                        strcat(merged, words1[k]);
                    }
                    
                    // Add remaining words from second phrase
                    for (int k = 1; k < count2; k++) {
                        strcat(merged, " ");
                        strcat(merged, words2[k]);
                    }
                    
                    // Check for duplicates
                    int isDuplicate = 0;
                    for (int k = 0; k < resultCount; k++) {
                        if (strcmp(results[k], merged) == 0) {
                            isDuplicate = 1;
                            break;
                        }
                    }
                    
                    if (!isDuplicate) {
                        strcpy(results[resultCount++], merged);
                    }
                }
            }
        }
    }
    
    qsort(results, resultCount, sizeof(results[0]), compare);
    *returnSize = resultCount;
    
    char** returnArray = malloc(resultCount * sizeof(char*));
    for (int i = 0; i < resultCount; i++) {
        returnArray[i] = malloc(strlen(results[i]) + 1);
        strcpy(returnArray[i], results[i]);
    }
    
    return returnArray;
}

int main() {
    char input[MAX_LEN];
    fgets(input, sizeof(input), stdin);
    input[strcspn(input, "\n")] = 0;
    
    char phrases[MAX_PHRASES][MAX_LEN];
    int phrasesSize = 0;
    
    // Simple JSON parsing for array of strings
    char *start = strchr(input, '[');
    char *end = strrchr(input, ']');
    if (start && end) {
        start++;
        *end = 0;
        
        char *token = strtok(start, ",");
        while (token != NULL && phrasesSize < MAX_PHRASES) {
            // Remove quotes and spaces
            while (*token == ' ' || *token == '"') token++;
            char *endQuote = strrchr(token, '"');
            if (endQuote) *endQuote = 0;
            
            strcpy(phrases[phrasesSize++], token);
            token = strtok(NULL, ",");
        }
    }
    
    int returnSize;
    char** result = solution(phrases, phrasesSize, &returnSize);
    
    printf("[");
    for (int i = 0; i < returnSize; i++) {
        if (i > 0) printf(",");
        printf("\"%s\"", result[i]);
    }
    printf("]\n");
    
    return 0;
}

Time & Space Complexity

Time Complexity

⏱️

O(n² × m)

Nested loops check n×n pairs, each taking O(m) time to process words where m is average phrase length

⚠ Quadratic Growth

Space Complexity

O(k × m)

Result set stores k merged phrases, each of average length m

✓ Linear Space

18.5K Views

Medium Frequency

~25 min Avg. Time

487 Likes

Ln 1, Col 1

Smart Actions

💡 Explanation

AI Ready

💡 Suggestion Tab to accept Esc to dismiss

// Output will appear here after running code

Code Editor Closed

Click the red button to reopen

Input & Output

Constraints

Visualization

Related Problems

Common Approaches

Brute Force — Algorithm Steps

Visualization

Code -

Time & Space Complexity

Select Compiler