Getting everything ready for you…

Loading courses, problems and your progress. This takes just a moment.

0s

Practice › Trie

Longest Word with All Prefixes

Medium · Trie · Asked at Google, Amazon, Pinterest

Find the longest word in the list such that every prefix of it is also in the list (for "apple": a, ap, app, appl must all be present). If several have the same length, print the lexicographically smallest. If no word qualifies, print None.

Input

First line: n. Second line: n lowercase words.

Output

The word, or None.

Constraints

Insert all words into a trie; then DFS only through nodes that end a word.

Example 1

Input

7
a banana app appl ap apply apple

Output

apple

Example 2

Input

3
ab abc bcd

Output

None

Hints

  1. Insert every word into a trie and mark the nodes where words end.
  2. A word qualifies exactly when every node on its path is marked as a word end. DFS only through marked nodes.

Approach

Build the trie. Starting from the root, DFS into a child only if that child ends a word — so every string reached has all its prefixes present. Visit children in alphabetical order and replace the best answer only when the current string is strictly longer; that way, among equal lengths the alphabetically first one (visited first) is kept. If no letter at depth 1 is a word, the answer is "None".

Complexity: O(total length) time · O(total length · 26) space

Solution

C++ solution

#include <bits/stdc++.h>
using namespace std;

struct TrieNode {
    int next[26];
    bool end = false;
    TrieNode() { memset(next, -1, sizeof next); }
};
vector<TrieNode> t(1);
string best, cur;

void dfs(int node) {
    if (cur.size() > best.size()) best = cur;
    for (int c = 0; c < 26; c++) {
        int nx = t[node].next[c];
        if (nx >= 0 && t[nx].end) {
            cur.push_back(char('a' + c));
            dfs(nx);
            cur.pop_back();
        }
    }
}

int main() {
    int n;
    cin >> n;
    for (int i = 0; i < n; i++) {
        string w;
        cin >> w;
        int node = 0;
        for (char c : w) {
            if (t[node].next[c - 'a'] < 0) {
                t[node].next[c - 'a'] = t.size();
                t.emplace_back();
            }
            node = t[node].next[c - 'a'];
        }
        t[node].end = true;
    }
    dfs(0);
    cout << (best.empty() ? "None" : best) << "\n";
    return 0;
}

Python solution

import sys

sys.setrecursionlimit(300000)
data = sys.stdin.read().split()
root = {}
for w in data[1 : 1 + int(data[0])]:
    node = root
    for c in w:
        node = node.setdefault(c, {})
    node["$"] = True
best = ""
stack = [(root, "")]
while stack:
    node, cur = stack.pop()
    if len(cur) > len(best) or (len(cur) == len(best) and cur < best):
        best = cur
    for c, child in node.items():
        if c != "$" and "$" in child:
            stack.append((child, cur + c))
print(best or "None")

Java solution

import java.util.*;

public class Main {
    static class TrieNode {
        TrieNode[] next = new TrieNode[26];
        boolean end;
    }

    static String best = "";
    static StringBuilder cur = new StringBuilder();

    static void dfs(TrieNode node) {
        if (cur.length() > best.length()) best = cur.toString();
        for (int c = 0; c < 26; c++) {
            TrieNode nx = node.next[c];
            if (nx != null && nx.end) {
                cur.append((char) ('a' + c));
                dfs(nx);
                cur.deleteCharAt(cur.length() - 1);
            }
        }
    }

    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        int n = sc.nextInt();
        TrieNode root = new TrieNode();
        for (int i = 0; i < n; i++) {
            TrieNode node = root;
            for (char c : sc.next().toCharArray()) {
                if (node.next[c - 'a'] == null) node.next[c - 'a'] = new TrieNode();
                node = node.next[c - 'a'];
            }
            node.end = true;
        }
        dfs(root);
        System.out.println(best.isEmpty() ? "None" : best);
    }
}

Solve Longest Word with All Prefixes online · All practice problems