Abstract / Summary

Given a list of words find the longest possible sequence where each word is formed by adding one letter to a previous word in the sequence

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 63% (800k+ submissions).

Typical patterns to solve this problem:

• Array
• Dynamic Programming
• Hash Table
• Sorting
• String
• Two Pointers

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 implementation computes the length of the longest possible word chain from a list of strings. A word chain is formed by repeatedly removing a single character from a word to obtain its predecessor, with each predecessor also present in the original list. The algorithm proceeds from the longest words toward the shortest, propagating chain lengths backward while maintaining the best result found.

Grouping Words by Length

The first phase builds a mapping from word length to the set of words having that length. This enables constant-time checks for the existence of a potential predecessor.

lengths = defaultdict(set)
for w in words:
    lengths[len(w)].add(w)

By storing words in a set, membership tests (in) are O(1) on average, which is crucial for the inner loop that examines many candidate predecessors.

Initialization of State

Two variables are prepared before the main loop. result holds the best chain length discovered so far, starting at 1 because any single word forms a trivial chain. longest records the maximum word length present, establishing the starting point for the backward traversal. The dictionary todo maps each word of maximal length to a chain length of 1, representing the base case for those words.

result  = 1
longest = max(lengths)
todo    = { w: 1 for w in lengths[longest] }

Iterative Reduction of Length

The core of the algorithm is a while loop that decrements longest until it reaches 1. At each iteration, the algorithm attempts to link the current set of words (todo) to shorter words one character smaller.

while longest > 1:
    next = {}
    ...
    longest -= 1
    ...
    todo = next

The loop structure guarantees that every word length is processed exactly once, moving from longer to shorter words.

Updating Chain Lengths

Inside the loop, each word in todo is examined. For every possible removal position i, a candidate predecessor shorter is generated by slicing out the character at i. If this candidate exists in the set of words of length len(w) - 1, the algorithm updates the next dictionary with a chain length that is one greater than the current word’s chain length. The max function ensures that, when multiple longer words converge on the same predecessor, the longest possible chain is retained.

for w in todo:
    for i in range(len(w)):
        shorter = w[:i] + w[i+1:]
        if shorter in lengths[len(w) - 1]:
            if shorter in next:
                next[shorter] = max(next[shorter], todo[w] + 1)
            else:
                next[shorter] = todo[w] + 1
            result = max(result, next[shorter])

After processing all current words, the algorithm ensures that any word of the new target length that did not receive a chain length from a longer word is assigned a default chain length of 1. This step guarantees that every word participates in the subsequent iteration.

for w in lengths[longest]:
    if w not in next:
        next[w] = 1

Edge Cases Handled

The design naturally accommodates several boundary conditions:

• When the input contains only one word, longest equals the length of that word, todo holds a single entry, and the loop terminates after the first decrement, leaving result at 1.
• If multiple words share the same maximal length, each is initialized with a chain length of 1, and the algorithm explores all possible predecessor paths in parallel.
• Words that have no valid predecessor are still represented in the next dictionary with a chain length of 1, ensuring they are considered when evaluating shorter words.
• The inner slicing operation works correctly for words of length 1, producing an empty string that will never be found in lengths[0], so such words simply retain a chain length of 1.

Performance Optimizations

The implementation incorporates several techniques that reduce computational overhead:

• Grouping words by length using a defaultdict(set) eliminates the need to scan the entire list when checking for a predecessor, turning each existence test into a constant-time operation.
• The backward iteration from longest to shortest avoids redundant recomputation of chain lengths for the same word, because each word’s best chain length is computed exactly once when it becomes the target of a longer word.
• Storing intermediate chain lengths in dictionaries (todo and next) provides O(1) access and update, and the use of max to merge multiple contributions prevents the need for additional passes.
• By assigning a default chain length of 1 to words that lack a predecessor, the algorithm sidesteps conditional checks later in the loop, keeping the inner logic tight.
• The overall flow processes each word a limited number of times proportional to its length, and the slicing operation creates new strings only when a potential predecessor is examined, which is unavoidable for this problem domain.

Imagine a big box of word blocks. The goal is to see how long of a chain can be built by picking a word and then finding a smaller word that fits perfectly inside it by removing just one letter.

First, all the words are sorted into piles based on how many letters they have. There is a pile for words with one letter, another for two, and so on up to the longest words.

A list is created to keep track of the chains starting from the longest words. Each long word starts with a chain length of one. The computer looks at each big word and tries taking away one letter at a time to see if the result exists in the pile of shorter words. If a matching shorter word is discovered, it means the chain has grown. The computer remembers how long this new chain is for that smaller word.

After checking all the big words, the computer moves to the next pile of smaller words. It keeps track of the best chain found so far and uses that information to see if it can keep building even longer chains as it works its way down to the tiny one-letter words. By the end of this process, the biggest chain found is the final answer.

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++	Python		Java				TS
	WalkCCC	C++	Python		Java
	leetcode.ca	C++	Python		Java		Go	Rust	TS
	LeetcodeHelp	C++	Python		Java
	Progiez	C++	Python		Java
github	BigEggStudy					C#
	black-shadows	C++
	charles-wangkai				Java
	everthis			JS
	fpdjsns	C++
	fsq	C++
	Garvit244		Python
	halfrost						Go
	JoshCrozier			JS
	keineahnung2345	C++
	lkwq007		Python
	suxrobGM					C#
	trung-hn		Python
	varunu28				Java
AlgoMonster	C++, Python, Java, TypeScript
WalkCCC	C++, Python, Java
leetcode.ca	C++, Go, Java, Python, Rust, TypeScript
LeetcodeHelp	C++, Java, Python
Progiez	C++, Java, Python
BigEggStudy	C#
black-shadows	C++, C++
charles-wangkai	Java
everthis	JavaScript
fpdjsns	C++
fsq	C++
Garvit244	Python
halfrost	Go
JoshCrozier	JavaScript
keineahnung2345	C++
lkwq007	Python
suxrobGM	C#
trung-hn	Python
varunu28	Java

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