L3. Longest Word With All Prefixes | Complete String | Trie

This chapter covers the third problem in the Trie Data Structure playlist: finding the Complete String (the longest string in a given array for which every prefix is also present in the array). If multiple longest strings tie in length, the lexicographically smallest one must be returned. If no such string exists, the algorithm returns none.

1. Why Do We Need This? (Problem Statement & Status Quo)

Given an array of strings $A$, we need to identify a string where every single prefix leading up to it is also a valid string in $A$.

• Definition of Complete String: A string $S$ is a complete string if all its prefixes ($S[0\dots 0]$, $S[0\dots 1]$, $\dots$, $S[0\dots \vert S\vert -1]$) exist as independent words within the array $A$.
• Tie-Breaking Rule:
  1. Return the longest complete string.
  2. If lengths are equal, return the lexicographically smallest string.
  3. If no complete string exists, return none.

Example Walkthrough

• Input Array: ["n", "ni", "nin", "ninj", "ninja", "ninga"]
• Prefix Verification:
  • For "ninja": Prefixes are "n", "ni", "nin", "ninj", and "ninja". All of these exist in the input array. Thus, "ninja" is a complete string.
  • For "ninga": Prefixes are "n", "ni", "nin", "ning", and "ninga". "ning", however, does not exist in the array. Thus, "ninga" is not a complete string.
• Result: "ninja" is identified as the longest complete string.

2. Core Mental Model & Analogy

Real-Life Analogy: The Building Blocks of Words

Imagine building a tower of toy blocks where each block represents a character. You are only allowed to step onto the next level if the block beneath it forms a complete, validated sub-word.

In a Trie structure, as we insert words, we mark the ending node of every valid word with a boolean flag (isEnd = true). To check if a word is a "complete string," we traverse its characters from root to leaf, ensuring that every single character node along the path has its isEnd flag set to true. If any node along the path lacks this flag, the chain is broken, meaning a required prefix is missing.

3. Naive vs. Better Approach

4. Step-by-Step Evolution: Trie Construction

To solve this efficiently, we leverage Lectures 1 and 2 of the Trie series. We need:

1. Trie Node Structure: An array of links of size 26 (links[26]) and a boolean flag (flag) representing whether a word ends at the current character.
2. Insertion Phase: Insert every word from the array into the Trie. Every time a word finishes, mark the final node's flag = true.

Insertion Trace Example (["n", "ninja", "ninj", "nin", "ninga"])

1. Insert "n":
   • Root -> Link for 'n' is created (flag = false).
   • Reaching the end of "n", mark 'n' node's flag = true.
2. Insert "ninja":
   • Root -> 'n' (already exists, move down).
   • Create 'i' (flag = false).
   • Create 'n' (flag = false).
   • Create 'j' (flag = false).
   • Create 'a' (flag = false).
   • Mark terminal 'a' node's flag = true.
3. Repeat similarly for "ninj", "nin", and "ninga".

5. Checking for Complete Strings

After inserting all words into the Trie, we iterate through each word in the original array and validate whether it qualifies as a complete string.

Validation Algorithm

For each string word:

1. Initialize a pointer at the root.
2. Traverse character by character (ch):
   • Check if the Trie contains a link for ch.
   • Check if the target node's flag is true.
3. If at any point a link does not exist or flag == false, the string is not a complete string.
4. If all characters pass, compare the valid complete string against our running longest candidate:
   • If current.length() > longest.length(), update longest = current.
   • If lengths are equal, pick the lexicographically smaller string.

6. Complete Flow Walkthrough

7. Complexity Analysis

• Time Complexity:
  • Insertion Phase: $O(N \cdot L)$, where $N$ is the number of strings and $L$ is the average length of a string.
  • Search/Validation Phase: $O(N \cdot L)$ to check every string's prefixes.
  • Total Time Complexity: $O(N \cdot L)$.
• Space Complexity:
  • $O(N \cdot L)$ in the average case for Trie nodes. In the worst-case scenario without shared prefixes, it scales with alphabet size ($26$ branches per node), though shared prefixes in real-world datasets significantly compress this footprint.

8. Reference Code Implementation

C++ Implementation

struct Node {
    Node* links[26];
    bool flag = false;

    bool containsKey(char ch) {
        return (links[ch - 'a'] != NULL);
    }

    void put(char ch, Node* node) {
        links[ch - 'a'] = node;
    }

    Node* get(char ch) {
        return links[ch - 'a'];
    }

    void setEnd() {
        flag = true;
    }

    bool isEnd() {
        return flag;
    }
};

class Trie {
private:
    Node* root;
public:
    Trie() {
        root = new Node();
    }

    void insert(string word) {
        Node* node = root;
        for (int i = 0; i < word.length(); i++) {
            if (!node->containsKey(word[i])) {
                node->put(word[i], new Node());
            }
            node = node->get(word[i]);
        }
        node->setEnd();
    }

    bool checkIfPrefixExists(string word) {
        Node* node = root;
        bool flag = true;
        for (int i = 0; i < word.length(); i++) {
            if (node->containsKey(word[i])) {
                node = node->get(word[i]);
                flag = flag & node->isEnd();
            } else {
                return false;
            }
        }
        return flag;
    }
};

string completeString(int n, vector<string> &a) {
    Trie obj;
    for (auto &word : a) {
        obj.insert(word);
    }
    string longest = "";
    for (auto &word : a) {
        if (obj.checkIfPrefixExists(word)) {
            if (word.length() > longest.length()) {
                longest = word;
            } else if (word.length() == longest.length() && word < longest) {
                longest = word;
            }
        }
    }
    if (longest == "") return "None";
    return longest;
}

Java Implementation

class Node {
    Node[] links = new Node[26];
    boolean flag = false;

    public boolean containsKey(char ch) {
        return links[ch - 'a'] != null;
    }

    public void put(char ch, Node node) {
        links[ch - 'a'] = node;
    }

    public Node get(char ch) {
        return links[ch - 'a'];
    }

    public void setEnd() {
        flag = true;
    }

    public boolean isEnd() {
        return flag;
    }
}

class Trie {
    private static Node root;

    public Trie() {
        root = new Node();
    }

    public void insert(String word) {
        Node node = root;
        for (int i = 0; i < word.length(); i++) {
            char ch = word.charAt(i);
            if (!node.containsKey(ch)) {
                node.put(ch, new Node());
            }
            node = node.get(ch);
        }
        node.setEnd();
    }

    public boolean checkIfPrefixExists(String word) {
        Node node = root;
        boolean flag = true;
        for (int i = 0; i < word.length(); i++) {
            char ch = word.charAt(i);
            if (node.containsKey(ch)) {
                node = node.get(ch);
                flag = flag & node.isEnd();
            } else {
                return false;
            }
        }
        return flag;
    }
}

class Solution {
    public static String completeString(int n, String[] a) {
        Trie obj = new Trie();
        for (String word : a) {
            obj.insert(word);
        }
        String longest = "";
        for (String word : a) {
            if (obj.checkIfPrefixExists(word)) {
                if (word.length() > longest.length()) {
                    longest = word;
                } else if (word.length() == longest.length() && word.compareTo(longest) < 0) {
                    longest = word;
                }
            }
        }
        if (longest.equals("")) return "None";
        return longest;
    }
}

Summary and Key Takeaways

• Problem Objective: Find the longest string in an array where every prefix of that string also exists in the array, breaking ties lexicographically.
• Trie Utilization: Inserting all words into a Trie allows us to validate prefixes in linear time relative to word lengths.
• Validation Flag: The boolean flag (isEnd) marks the exact termination point of valid words inserted during the pre-processing phase.
• Prefix Integrity Check: A string is only a complete string if traversing its characters visits nodes where every single node has its ending flag marked true.
• Lexicographical Tie-Breaking: When two complete strings share the maximum length, string comparison operators (< in C++, compareTo() in Java) determine the lexicographically smaller result.
• Optimal Efficiency: The combined insertion and prefix-checking pipeline executes in $O(N \cdot L)$ time, bypassing slow brute-force subset searches.