Longest word built one letter at a time

Why this matters

A word game gives you a pile of words and asks for the longest word you can build one letter at a time. Each step must give a word that is also in the pile. Word games and spell-checking tools use checks like this. A plain list of words answers the question slowly, because for each candidate you must check every shorter piece of it. A trie answers it in one walk.

This lesson uses the trie from the earlier lessons in this module and a depth-first search, which is a walk that goes as deep as it can down one branch before it tries the next. The new idea is small. A node in a trie can be a path that leads somewhere, or it can be a word. The code must tell those two cases apart. Most bugs in this lesson come from mixing them up.

The problem in plain words

A prefix of a word is its first few letters. "app" is a prefix of "apple", and "a" is a prefix of "apple" too. The empty prefix (no letters) is always allowed, so we ignore it.

A word is buildable when every one of its prefixes is also a word in the pile. Take this pile: a, banana, app, appl, ap, apple, apply.

• "apple" is buildable. Its prefixes are "a", "ap", "app" and "appl", and all four are in the pile.
• "banana" is not buildable. Its first prefix is "b", and "b" is not in the pile.
• "apply" is buildable. Its prefixes are "a", "ap", "app" and "appl", all in the pile.

The task is to find the longest buildable word. If two buildable words have the same length, the answer is the one that comes first in alphabetical order. If no word is buildable, the answer is the empty string. The empty string is the answer when the pile does not contain a single letter word.

Here is a second example. The pile is w, wo, wor, worl, world. Each prefix of "world" is in the pile: "w", "wo", "wor" and "worl". So the answer is "world". Each step adds one letter and stays a word, which is what "built one letter at a time" means.

Step 1: Mark the word ends

A trie stores words letter by letter in a tree. Each node stands for one prefix. The root stands for the empty prefix. The node reached by "ap" stands for the prefix "ap".

There is a catch. A node can exist only because a longer word passes through it. Insert the single word "apple". The trie now has nodes for "a", "ap", "app", "appl" and "apple". Only "apple" is a stored word. If we ask "is app a word?" by checking whether the node exists, the answer is wrong. The node exists, but no one stored "app".

The fix is one flag per node. Call it is_end. It is true only when a stored word ends at that node. Here is the state after inserting "apple" alone:

Now insert "app" as well. The node for "app" exists already, so no new node is made. Its flag changes to true, and the other nodes are unchanged. The flag is the only thing that separates "a path in the trie" from "a word in the pile".

The node struct holds the flag and the links to children:

struct Node {
    std::array<int, 26> next{};  // index of the child for each letter; 0 means no child
    bool is_end = false;         // true if a stored word ends at this node
};

There are 26 slots in next, one for each lowercase letter. The letter c goes to slot c - 'a', which is 2. The nodes live in a std::vector<Node>, and a child is stored as its index in that vector. The root is node 0. No node is ever a child of the root's index 0, so the value 0 can mean "no child" without confusion. This keeps the code free of pointers, and a vector does not give dangling pointers when it grows.

Step 2: Walk only through marked nodes

The search starts at the root. For each letter, it looks at the child for that letter. It steps into the child only when the child's flag is set.

Why does skipping work? A buildable word needs every prefix to be a word. If a node is not a word, then no word below it can be buildable, because the word would need that node's prefix in the pile. So when we find an unmarked node, we can skip its whole subtree. This is called pruning, which means cutting off a branch you know cannot help.

Here is a trace with the pile yes, ye, y, yesterday. The trie has a branch that goes y, ye, yes, yest, yeste, and so on down to "yesterday". Only some of those nodes are words.

The walk never reaches "yesterday", because "yest" is not in the pile. The answer is "yes", not "yesterday". Notice that the trie still holds all the letters of "yesterday". The search does not look at them, because the flags stop it at "yest".

The search itself is a function that takes a node, the path of letters so far, and the best word found so far:

void dfs(int node, std::string& path, std::string& best) const {
    if (path.size() > best.size()) {
        best = path;
    }
    for (int i = 0; i < 26; ++i) {
        int child = nodes_[node].next[i];
        if (child != 0 && nodes_[child].is_end) {
            path.push_back(static_cast<char>('a' + i));
            dfs(child, path, best);
            path.pop_back();
        }
    }
}

Every node the function enters is a stored word, so the current path is always a buildable word. That is why the length check at the top is enough. It does not need to check the prefixes again.

The path string is shared between calls. Before a call goes down one letter, it pushes that letter. After the call returns, it pops the letter. This way one string serves the whole walk and the code never copies it at each step.

Step 3: Choose among words of the same length

Two buildable words can have the same length. In the first example, "apple" and "apply" both have five letters. The problem asks for the alphabetically smaller one, which is "apple".

The depth-first search gives the right order for free. It tries the letters from "a" to "z" in the loop, and it handles a word before the longer words that start with it. So the words come out in alphabetical order. The first word of the longest length it finds is therefore the smallest one of that length. The code only replaces best when a candidate is strictly longer:

if (path.size() > best.size()) {
    best = path;
}

Why is "apple" before "apply"? The two words share "appl". The next letters are "e" and "y". The letter "e" comes before "y" in the alphabet, and the search tries "e" first. So "apple" is found first, and "apply" has the same length but is not strictly longer, so it does not replace the answer.

A worked example makes this clearer. Take the full pile from the first example, a, banana, app, appl, ap, apple, apply, and suppose the code used >= instead. Then each equal-length word would replace the answer, and the last one in alphabetical order would win. That gives "apply". The rule is strict greater-than because we want the first word found, which is the smallest.

Worked example 1: a list with a blocked branch

The pile is c, ca, cat, cats, car, cars, cart, carts, cared. Here is what the trie walk finds.

• "c", "ca" and "car" are words, so the search enters them.
• Below "car" there are three words: "cars", "cart" and "carts". The search enters all of them, because each one is a word and its prefixes are words.
• "carts" has five letters. Its prefixes are "c", "ca", "car", "cart" and "carts", and all are in the pile. It is buildable.
• "cared" also has five letters, so it ties with "carts" on length. But its prefix "care" is not in the pile, so the search never enters the node for "cared". The branch is blocked.

The output is:

answer: "carts"

This example shows that length alone is not enough. "cared" is as long as "carts", yet it is not buildable. A solution that only looks for the longest word in the trie would give the wrong answer here.

Worked example 2: no single letter at all

The pile is cat and cats. Neither is a single letter, and "c" is not in the pile. Every word needs "c" as its first step, so no word is buildable. The walk from the root finds no child that is a word, so it never goes down, and the answer stays empty.

answer: ""

The output is two double quotes with nothing between them. That is the empty string, which the problem uses for "no answer".

A related case is the pile a, ab, abcd, b. The word "abcd" has the prefixes "a", "ab" and "abc", but "abc" is missing. The search reaches "ab", which is a word, and stops there, because "abc" is not a word. The answer is "ab", which is the longest buildable word.

The full program

Here is the whole program. It has the trie class, the search, and three examples. Save it as longest.cpp.

#include <array>
#include <iostream>
#include <string>
#include <string_view>
#include <vector>
 
struct Node {
    std::array<int, 26> next{};  // index of the child for each letter; 0 means no child
    bool is_end = false;         // true if a stored word ends at this node
};
 
class Trie {
public:
    Trie() : nodes_(1) {}  // node 0 is the root
 
    void insert(std::string_view word) {
        int cur = 0;
        for (char c : word) {
            int i = c - 'a';
            if (nodes_[cur].next[i] == 0) {
                nodes_[cur].next[i] = static_cast<int>(nodes_.size());
                nodes_.emplace_back();
            }
            cur = nodes_[cur].next[i];
        }
        nodes_[cur].is_end = true;
    }
 
    // Longest stored word whose every prefix is also a stored word.
    // Ties go to the alphabetically smaller word.
    std::string longest_buildable() const {
        std::string best;
        std::string path;
        dfs(0, path, best);
        return best;
    }
 
private:
    void dfs(int node, std::string& path, std::string& best) const {
        // Every node we enter is a stored word, so path is a valid candidate.
        if (path.size() > best.size()) {
            best = path;
        }
        for (int i = 0; i < 26; ++i) {
            int child = nodes_[node].next[i];
            // Only go down into a child that is itself a stored word.
            if (child != 0 && nodes_[child].is_end) {
                path.push_back(static_cast<char>('a' + i));
                dfs(child, path, best);
                path.pop_back();
            }
        }
    }
 
    std::vector<Node> nodes_;
};
 
std::string solve(const std::vector<std::string>& words) {
    Trie trie;
    for (const std::string& w : words) {
        trie.insert(w);
    }
    return trie.longest_buildable();
}
 
int main() {
    std::vector<std::vector<std::string>> examples = {
        {"w", "wo", "wor", "worl", "world"},
        {"a", "banana", "app", "appl", "ap", "apple", "apply"},
        {"yes", "ye", "y", "yesterday"},
    };
    for (const auto& words : examples) {
        std::cout << "answer: \"" << solve(words) << "\"\n";
    }
}

Compile and run it with:

g++ -std=c++20 -Wall -Wextra -o longest longest.cpp
./longest

The output is:

answer: "world"
answer: "apple"
answer: "yes"

The program compiles with no warnings under -Wall -Wextra. The insert function builds the path for each word. The solve function builds one trie and asks it for the answer. Each call to solve starts with a new trie, so the examples do not affect each other.

The search enters each buildable node once and checks the 26 slots of each node it enters. So its work grows with the number of nodes it enters, and the flag check keeps it away from the rest of the trie.

Common mistakes

Forgetting the end flag

The most common bug is to enter every child, not only the marked ones. The search then follows every path in the trie, and any stored word's path counts as buildable.

Here is the change, done on a copy of the program. The condition in dfs becomes if (child != 0). Running the three examples gives:

answer: "world"
answer: "banana"
answer: "yesterday"

The answer "banana" is wrong, because "b" is not in the pile. The trie has nodes for "b", "ba" and "ban", because "banana" passes through them. Without the flag check, the search walks through them. The same error gives "yesterday" for the third pile, which is wrong for the same reason.

The fix is to test the flag on the child before entering it. A node in the trie is not enough to make a word.

Using greater-or-equal for the tie

The answer to the tie rule is found by a strict comparison. If the code uses >= instead of >, each equal-length word replaces the current answer. The last one in alphabetical order wins. The second example then prints:

answer: "apply"

The problem asks for "apple", so this is wrong. The bug is easy to miss, because the output is still a valid buildable word of the right length.

Forgetting the letter offset

Each slot in next is found with c - 'a'. If the code writes int i = c; instead, the index is the character code, which is 97 for "a" and more for later letters. That index is past the end of the array of 26 slots.

Compiling a copy of the program with -Wall gives no warning. Building it with the address sanitizer, which is a runtime checker that finds bad memory use, and running it gives this output:

/usr/include/c++/15/array:210: constexpr std::array<_Tp, _Nm>::value_type& std::array<_Tp, _Nm>::operator[](size_type) [with _Tp = int; long unsigned int _Nm = 26; reference = int&; size_type = long unsigned int]: Assertion '__n < this->size()' failed.

The build command was g++ -std=c++20 -Wall -g -fsanitize=address -o longest_noffset longest_noffset.cpp, and the program exited with code 134, which means it was stopped by an abort. The message comes from the C++ library, which checked the index and found it too large. Without such a check, the same bad index can read or write memory the program does not own, and the program may appear to work.

Practice

Exercise 1. The pile is a, ab, abc, b. What is the answer?

Show the answer

The answer is "abc". Its prefixes are "a", "ab" and "abc", and all three are in the pile. It has three letters, which is the longest length in this pile.

Exercise 2. The pile is x, xy, xyz, xyzww. What is the answer, and why not "xyzww"?

Show the answer

The answer is "xyz". The word "xyzww" has the prefix "xyzw", and "xyzw" is not in the pile, so the word is blocked. The search stops at "xyz".

Exercise 3. The pile is a, ab, abcd, b. How many words in the pile are buildable?

Show the answer

Three words are buildable: "a", "ab" and "b". The word "abcd" is not, because its prefix "abc" is missing. A single letter counts as buildable when it is in the pile, because its only prefix is itself.

Exercise 4. The pile is cat, cats. What does the program print?

Show the answer

It prints answer: "". There is no single letter in the pile, so no word can start. The answer is the empty string.

Exercise 5. Change the program so that, among the words of the longest length, it returns the alphabetically largest one. Which operator changes?

Show the answer

Change the comparison in dfs from > to >=. Each equal-length word then replaces the answer, and the last one in alphabetical order stays. For the pile a, ap, app, appl, apple, apply, the output changes from "apple" to "apply". This is the same change that the mistake section shows as a bug, so it is only a bug when the problem asks for the smallest word.

Summary

• A trie node can be a path or a word. The is_end flag tells the two apart.
• A word is buildable when every one of its prefixes is also a word, and the search only enters nodes whose flag is set.
• Skipping an unmarked node skips its whole subtree, which is pruning.
• A depth-first search tries letters from "a" to "z", so words come out in alphabetical order. Replacing the answer only when strictly longer keeps the smallest word of the longest length.
• Test the flag on each child before entering it, and check that each letter index is between 0 and 25.