Abstract / Summary

Find the longest word in a list that can be built one letter at a time using other words in the list.

Note

The full problem description, including helpful examples, can be found on LeetCode.

This problem is ranked as

and has an acceptance rate of about 55% (300k+ submissions).

Typical patterns to solve this problem:

• Array
• Hash Table
• Sorting
• String
• Trie

Every single line of code was written by me, 100% from scratch, between August 2023 and August 2024.
However, two years later I set up this website and used various AI tools to generate most of the walkthrough / explanations below.

See this dedicated page for more details.

Overview

The provided Solution class implements a method longestWord that receives a list of strings and returns the longest string that can be constructed by successively removing its last character until an empty string is reached, with each intermediate prefix required to exist in the original list. When multiple candidates share the maximum length, the lexicographically smallest one is chosen.

Key Steps

The algorithm begins by initializing an empty result string and converting the input list into a set for constant-time membership checks.

result = ""
all = set(words)

It then iterates over each word in the original order. The first conditional skips any word whose length is already shorter than the current best result, ensuring that only potentially better candidates are examined.

for w in words:
    if len(w) < len(result):
        continue

For each remaining word, a loop repeatedly truncates the last character, checking whether the truncated version still appears in the original list. The loop stops when a truncated form is missing, leaving shorter either empty (indicating a valid chain) or non-empty (indicating failure).

shorter = w
while shorter in words:
    shorter = shorter[:-1]
if shorter:
    continue

If the word passes the prefix chain test, the algorithm updates the result. When the candidate is longer than the current result, it becomes the new result. If the lengths are equal, the lexicographically smaller word is retained using min.

if len(w) > len(result):
    result = w
else:
    result = min(result, w)

Finally, the method returns the selected word.

return result

Edge Cases Handled

The implementation gracefully handles an empty input list: the initial result remains an empty string and is returned unchanged. When the list contains words of identical maximum length, the lexicographic comparison via min guarantees that the smallest word is chosen. The early length check prevents unnecessary processing of shorter words, which also covers the scenario where the longest valid word appears early in the list. Additionally, the while-loop termination condition ensures that words lacking a full chain of prefixes are excluded, even if they are long.

Performance Optimizations

A notable optimization is the creation of a set (all) from the input list, enabling O(1) membership tests during the prefix-validation loop. The early continue based on length reduces the number of words subjected to the more expensive truncation checks. By reusing the same variable shorter for successive truncations, the code avoids allocating additional strings beyond what Python’s slicing already provides. The final comparison logic avoids extra sorting or additional data structures, directly updating the result in constant time per qualifying word.

Imagine playing a game where you want to build the longest tower of blocks possible. In this game, each block has a letter on it, and to build a word, you have to add letters one by one. You start with a tiny one-letter word, then add another letter to make a two-letter word, and keep going as long as every version of your word exists in the pile of words you have.

The code starts by looking at all the words in the pile. It picks up one word at a time to see if it can be the base of a long tower. It checks if the word is long enough to beat the best word found so far. To see if a word is good, the code takes the last letter off, then the next last letter, and keeps doing that to see if every smaller piece is also inside the pile of words. If it finds all the pieces, that word is a builder.

If the word is a builder, the code compares it to the previous best word. If the new builder is longer, it becomes the new winner. If it is the same length, the code picks the word that would come first in a dictionary. By the time the code finishes checking every word, it knows which one is the champion word.

Several LLMs ranked my code quality on a scale from 1 (very poor) to 10 (outstanding):

Time: polynomial
As a rule of thumb, the maximum input size for one second execution time is

• factorial: up to 10 elements
• exponential: up to 20 elements
• polynomial: a few thousand elements
• loglinear: up to 100,000 elements
• linear: a few million elements
• logarithmic: a billion elements
• constant: practically unlimited

I wrote a basic crawler to find other solutions to that problem.
Obviously, I did that after I solved the problem myself.

In general, AlgoMonster and WalkCCC solutions are high-quality and always worth a look.
I haven't checked most of the other solutions, but they might be helpful as well.

And of course, the LeetCode forum is always a good place (or even the best) to look for alternative approaches.

(click on a column header to sort the table)

	author
author	solutions
www	AlgoMonster	C++	Java		Python						TS
	WalkCCC	C++	Java		Python
	leetcode.ca	C++	Java		Python	JS		Rust		Go	TS
	LeetcodeHelp	C++	Java		Python
	MemoryLimitExceeded	C++			Python
	Progiez	C++	Java		Python
github	BigEggStudy			C#
	black-shadows	C++
	charles-wangkai		Java
	everthis					JS
	fartem								Ruby
	fengvyi	C++
	halfrost									Go
	JoshCrozier					JS
	keineahnung2345	C++
	lkwq007				Python
	lzl124631x	C++
	martianoff						Scala
	qiyuangong		Java
	ruoru							Rust
	shreymehul			C#
	suxrobGM			C#
	varunu28		Java
	YuriSpiridonov				Python
	zfang399	C++
AlgoMonster	C++, Python, Java, TypeScript
WalkCCC	C++, Python, Java
leetcode.ca	C++, Go, Java, JavaScript, Python, Rust, TypeScript
LeetcodeHelp	C++, Java, Python
MemoryLimitExceeded	Python, C++
Progiez	C++, Java, Python
BigEggStudy	C#
black-shadows	C++, C++
charles-wangkai	Java
everthis	JavaScript
fartem	Ruby
fengvyi	C++
halfrost	Go
JoshCrozier	JavaScript
keineahnung2345	C++
lkwq007	Python
lzl124631x	C++
martianoff	Scala
qiyuangong	Java
ruoru	Rust
shreymehul	C#
suxrobGM	C#
varunu28	Java
YuriSpiridonov	Python
zfang399	C++

There are a few extra pages giving you some insights into my setup:

• Tech Stack - my development environment and tools
• AI - how AI helped me create this website (NOT solving the problems)
• Progress - progression over time
• Quality - code quality