☕ DSA Java Articles

Topics › Tries › Problems

Longest Word with All Prefixes

Medium TUF ID 1023 A2ZSDE

LeetCode ↗ Java source ↗ Edit this article ↗

Problem

You are given an array of n lowercase strings. Call a string complete if every one of its prefixes, from length 1 up to its full length, also appears in the array. Return the longest complete string. If several complete strings share the maximum length, return the lexicographically smallest of them. If no string is complete, return "None".

A one-letter string is complete as soon as it is in the array, because its only prefix is itself. The empty prefix is never required. LeetCode 1858 asks the same question but returns "" instead of "None" when there is no answer; only the last line of each method changes.

Constraints: up to 10^5 strings whose lengths add up to at most 10^5.

Example 1

words  = ["n", "ni", "nin", "ninj", "ninja", "ninga"]
answer = "ninja"     // n, ni, nin, ninj, ninja are all present; "ninga" fails because "ning" is missing

Example 2

words  = ["a", "banana", "app", "appl", "ap", "apply", "apple"]
answer = "apple"     // "apple" and "apply" are both complete with length 5; "apple" is smaller

Example 3

words  = ["abc", "bc", "ab", "qwe"]
answer = "None"      // no one-letter word exists, so no word can be complete

Every approach keeps a running best and replaces it through the same rule: a longer string wins, and at equal length the lexicographically smaller one wins.

static boolean isBetter(String candidate, String best) {
    if (candidate.length() != best.length()) return candidate.length() > best.length();
    return candidate.compareTo(best) < 0;
}

Starting best at "" means any complete word of length at least 1 beats it, and an untouched "" at the end signals “no answer”.

Approach 1: Brute force

Intuition. Follow the definition literally. For each word, generate each prefix and scan the whole array to see whether it is there. The word is complete if every scan succeeds. This answers the question correctly but repeats the same array scan over and over.

Algorithm.

  1. For each word w, for len = 1..|w|: build w.substring(0, len) and scan the array for an equal string. Stop at the first prefix that is missing.
  2. If all prefixes were found and isBetter(w, best), set best = w.
  3. Return best, or "None" if it is still empty.
static String bruteForce(String[] words) {
    String best = "";
    for (String w : words) {
        boolean complete = true;
        for (int len = 1; len <= w.length() && complete; len++) {
            String prefix = w.substring(0, len);
            boolean found = false;
            for (String other : words) {
                if (other.equals(prefix)) {
                    found = true;
                    break;
                }
            }
            complete = found;
        }
        if (complete && isBetter(w, best)) best = w;
    }
    return best.isEmpty() ? "None" : best;
}

Complexity. Time O(n^2 · L^2) in the worst case: n words, L prefixes each, and each prefix compared against n strings at up to L characters per comparison. Space O(L) for the current prefix.

Approach 2: Better, a hash set of the words

Intuition. The inner scan answers “is this string in the array?”, which is exactly what a hash set answers in O(L). Put every word in a set once, and each prefix check becomes a lookup. The word itself is certainly in the set, so only proper prefixes, lengths 1..|w| - 1, need checking.

Algorithm.

  1. Insert all words into a HashSet.
  2. For each word, check set.contains(w.substring(0, len)) for len = 1..|w| - 1, stopping early on a miss.
  3. Update best with isBetter and return as before.
static String better(String[] words) {
    Set<String> set = new HashSet<>(Arrays.asList(words));
    String best = "";
    for (String w : words) {
        boolean complete = true;
        for (int len = 1; len < w.length() && complete; len++) {   // w itself is in the set already
            complete = set.contains(w.substring(0, len));
        }
        if (complete && isBetter(w, best)) best = w;
    }
    return best.isEmpty() ? "None" : best;
}

Complexity. Time O(Σ |w|^2), which is O(n · L^2): a word of length L has L prefixes and each is copied and hashed in up to L steps. Space O(total characters) for the set.

The quadratic factor comes from rebuilding every prefix from scratch, although each prefix is just the previous one plus a letter. The early exit softens it, because a long check only happens when many prefixes are present, and those prefixes use up the input budget. But many long words can share one long chain of prefixes, and each of them pays again to copy and hash the whole chain. That is L^2 work per word where a single walk would cost L.

Approach 3: Optimal, a trie

Intuition. Insert all words into a trie and mark the node where each word ends. In a trie the node reached after i letters of w is the prefix of length i, and its end marker says whether that prefix is a word in the array. So “every prefix of w is in the array” is the same as “every node on w’s path is marked”. Checking it is one walk down the path, O(1) per letter, because moving to the next prefix is following one edge rather than building a new string.

Algorithm.

  1. Insert every word into a trie, setting isEnd on the node where it ends.
  2. For each word, walk its path from the root. If any node on the path is unmarked, the word is not complete.
  3. Among complete words keep the best by isBetter, and return it or "None".

The trie is the one from the basic trie problem, with only insert needed:

static class Node {
    final Node[] child = new Node[26];
    boolean isEnd;                                     // some word in the array ends exactly here
}

static void insert(Node root, String word) {
    Node cur = root;
    for (int i = 0; i < word.length(); i++) {
        int c = word.charAt(i) - 'a';
        if (cur.child[c] == null) cur.child[c] = new Node();
        cur = cur.child[c];
    }
    cur.isEnd = true;
}

The check walks the word and fails on the first unmarked node:

static boolean allPrefixesPresent(Node root, String word) {
    Node cur = root;
    for (int i = 0; i < word.length(); i++) {
        cur = cur.child[word.charAt(i) - 'a'];
        if (cur == null || !cur.isEnd) return false;   // the prefix of length i + 1 is not a word
    }
    return true;
}

static String optimal(String[] words) {
    Node root = new Node();
    for (String w : words) insert(root, w);
    String best = "";
    for (String w : words) {
        if (allPrefixesPresent(root, w) && isBetter(w, best)) best = w;
    }
    return best.isEmpty() ? "None" : best;
}

Dry run on Example 1. T means the node on the path is marked, F means it is not:

Word Marks along the path Complete? best afterwards
n T yes n
ni T T yes ni
nin T T T yes nin
ninj T T T T yes ninj
ninja T T T T T yes ninja
ninga T T T F (at “ning”) no ninja

Complexity. Building the trie and checking all words each read every character once, so O(Σ |w|), linear in the input size; the isBetter comparisons add at most O(L) per word, which is within the same bound. Space O(26 · Σ |w|) references in the worst case.

An equivalent way to finish is a depth-first search from the root that only steps into marked children, visiting letters a to z and recording a node only when it is strictly deeper than the best so far. Visiting in alphabetical order makes the first deepest node the lexicographically smallest one. The per-word walk above is shorter to write and easier to get right.

Edge cases and pitfalls