We use cookies (including Google cookies) to personalize ads and analyze traffic. By continuing to use our site, you accept our Privacy Policy.

SimplyLeet
TagsDisclaimersPrivacyTermsContactAbout Us

Longest Word With All Prefixes

Number: 2009

Difficulty: Medium

Paid? Yes

Companies: Google

Problem Description

Given an array of strings words, find the longest string such that every prefix of the string is also in words. If there are multiple answers with the same length, return the lexicographically smallest one. If no valid string exists, return an empty string.

Key Insights

  • Use a hash set for O(1) look-up to check if a prefix exists.
  • Sorting the list lexicographically ensures that when candidates of the same length are encountered, the lexicographically smallest word is chosen.
  • Iterate through each word and check if every prefix (from index 1 up to word.length-1) exists in the set.

Space and Time Complexity

Time Complexity: O(n * l) where n is the number of words and l is the maximum word length (since for each word all prefixes are checked)
Space Complexity: O(n * l) for storing words in a hash set

Solution

We solve the problem by first inserting all words into a hash set for quick prefix verification. Next, we sort the words lexicographically so that in cases of ties on the string length, the lexicographically smallest word is naturally considered first. For each word, we check if every prefix is present in the hash set. If a word passes this check and meets the conditions of being longer or lexicographically smaller (when lengths match), we update our result.

Code Solutions

# Python solution with inline comments

def longestWord(words):
    # Create a set from words for fast lookup
    word_set = set(words)
    valid_word = ""
    
    # Sort words lexicographically
    for word in sorted(words):
        # Check if every prefix (from index 1 to len(word)-1) exists in the set
        valid = True
        for i in range(1, len(word)):
            if word[:i] not in word_set:
                valid = False
                break
        # If current word is valid and is longer or same length but lexicographically smaller than current valid_word, update it
        if valid:
            if len(word) > len(valid_word) or (len(word) == len(valid_word) and word < valid_word):
                valid_word = word
    return valid_word

# Example usage:
print(longestWord(["k", "ki", "kir", "kira", "kiran"]))  # Output: "kiran"
print(longestWord(["a", "banana", "app", "appl", "ap", "apply", "apple"]))  # Output: "apple"
← Back to All Questions