Longest Word With All Prefixes - Practice Coding Problems

Longest Word With All Prefixes - Problem

Given an array of strings words, find the longest string in words such that every prefix of it is also in words.

For example, let words = ["a", "app", "ap"]. The string "app" has prefixes "ap" and "a", all of which are in words.

Return the string described above. If there is more than one string with the same length, return the lexicographically smallest one, and if no string exists, return "".

Input & Output

Example 1 — Basic Case

$ Input: words = ["a", "app", "ap"]

› Output: "app"

💡 Note: The word "app" has prefixes "a" and "ap", both exist in the array. "app" is the longest such word.

Example 2 — Multiple Valid Words

$ Input: words = ["w", "wo", "wor", "worl", "world"]

› Output: "world"

💡 Note: "world" has all prefixes "w", "wo", "wor", "worl" in the array. It's the longest valid word.

Example 3 — No Valid Word

$ Input: words = ["abc", "def", "ghi"]

› Output: ""

💡 Note: No word has all its prefixes in the array ("abc" needs "a", "ab" but they don't exist).

Constraints

1 ≤ words.length ≤ 1000
1 ≤ words[i].length ≤ 30
words[i] consists of lowercase English letters only

Visualization

Tap to expand

Understanding the Visualization

Input

Array of words: ["a", "app", "ap"]

Process

Check which words have all prefixes present

Output

Return longest valid word: "app"

Key Takeaway

🎯 Key Insight: Only words that can be built character-by-character from existing shorter words are valid candidates

Asked in

G Google 25 a Amazon 18 M Microsoft 12

The key insight is that a word can only be built if all its prefixes exist. The hash set approach offers good balance with O(n×m²) time by enabling O(1) prefix lookups. The trie + DFS approach is most elegant, building words incrementally. Best approach: Hash Set for simplicity, Trie for elegance. Time: O(n×m²), Space: O(n×m)

Common Approaches

Approach	Time	Space	Notes
✓ Brute Force with Prefix Checking	O(n² × m²)	O(1)	For each word, check if all its prefixes exist in the array
DFS with Trie	O(n × m)	O(n × m)	Build a trie and use DFS to find words that can be built character by character
Hash Set Optimization	O(n × m²)	O(n × m)	Use a hash set for O(1) prefix lookups instead of scanning the array

Brute Force with Prefix Checking — Algorithm Steps

For each word in the array
Generate all prefixes of the word
For each prefix, scan the array to check if it exists
If all prefixes exist, update the longest result

Visualization

Tap to expand

Step-by-Step Walkthrough

Pick Word

Select a word from the array

Check Prefixes

Verify each prefix exists in the array

Update Result

Keep the longest valid word

Code -

solution.c — C

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

char* solution(char words[][100], int n) {
    static char result[100] = "";
    
    for (int i = 0; i < n; i++) {
        int valid = 1;
        int wordLen = strlen(words[i]);
        
        // Check all prefixes of current word
        for (int j = 1; j < wordLen && valid; j++) {
            char prefix[100];
            strncpy(prefix, words[i], j);
            prefix[j] = '\0';
            
            int found = 0;
            for (int k = 0; k < n; k++) {
                if (strcmp(words[k], prefix) == 0) {
                    found = 1;
                    break;
                }
            }
            if (!found) {
                valid = 0;
            }
        }
        
        if (valid) {
            int resultLen = strlen(result);
            // Update result if this word is longer or lexicographically smaller
            if (wordLen > resultLen || (wordLen == resultLen && strcmp(words[i], result) < 0)) {
                strcpy(result, words[i]);
            }
        }
    }
    
    return result;
}

int main() {
    char line[1000];
    fgets(line, sizeof(line), stdin);
    
    // Simple parsing for JSON array
    char words[100][100];
    int n = 0;
    
    char* token = strtok(line, "[],\"\n");
    while (token != NULL && n < 100) {
        if (strlen(token) > 0 && token[0] != ' ') {
            strcpy(words[n], token);
            n++;
        }
        token = strtok(NULL, "[],\"\n");
    }
    
    char* result = solution(words, n);
    printf("%s\n", result);
    
    return 0;
}

Time & Space Complexity

Time Complexity

⏱️

O(n² × m²)

For each word (n), we check all prefixes (m), and for each prefix we scan the array (n×m)

⚠ Quadratic Growth

Space Complexity

O(1)

Only using constant extra space for variables

✓ Linear Space

23.5K Views

Medium Frequency

~25 min Avg. Time

890 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 with Prefix Checking — Algorithm Steps

Visualization

Code -

Time & Space Complexity

Select Compiler