Abstract / Summary

Given a list of words find the shortest total length when encoding words by using the first letter then the number of unique characters that follow for each word that is not a prefix of another.

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 61% (100k+ submissions).

Typical patterns to solve this problem:

• Array
• Hash Table
• 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 implementation computes the length of the shortest possible encoding for a list of words, where each word is terminated by a # character and words that are suffixes of other words can share the same terminating #. The algorithm works by reversing each word, sorting the reversed collection, and then scanning the sorted list while merging consecutive entries that share a prefix. The accumulated length, adjusted for merged prefixes, yields the minimal encoding size.

Key Steps

Reversing the Input Words

The first transformation creates a new list where every word is reversed. This conversion turns the suffix-relationship among original words into a prefix-relationship among the reversed strings, which is easier to detect after sorting.

reverse = [ w[::-1] for w in words ]

Sorting the Reversed Words

Sorting the reversed list places strings that share a common prefix next to each other. Because Python’s default sort is lexicographic, any group of strings where one is a prefix of another will appear consecutively, enabling a single linear pass to identify mergable words.

for r in sorted(reverse):

Initializing the Accumulator

Two variables are prepared before the scan begins. result holds the running total of the encoding length, while prev stores the previously processed reversed word. The placeholder "STOP" is chosen because it contains characters outside the allowed lowercase alphabet, guaranteeing that the first comparison will never trigger a merge.

result = 0
prev = "STOP"

Adding the Length of Each Word

For each reversed word r encountered in the sorted order, its length plus one (for the required # delimiter) is added to result. This step assumes that, in the worst case, every word contributes its full length to the final encoding.

result += len(r) + 1

Merging Overlapping Prefixes

After adding the length, the algorithm checks whether the current word r starts with the previous word prev. If prev is a prefix of r, the earlier addition for prev was unnecessary because prev is already represented as a suffix of r in the original orientation. Consequently, the length contributed by prev (including its #) is subtracted from result.

if len(prev) <= len(r) and r.startswith(prev):
    result -= len(prev) + 1

The condition also guards against cases where prev is longer than r, ensuring that only true prefix relationships trigger a subtraction.

Updating the Previous Word

At the end of each iteration, prev is set to the current word r, preparing the comparison for the next loop cycle.

prev = r

Returning the Final Length

When the loop finishes, result reflects the minimal total length of the encoded string, and it is returned to the caller.

return result

Edge Cases Handled

When the input list contains duplicate words, each duplicate is reversed and appears multiple times in the sorted sequence. The prefix-check logic ensures that only the first occurrence contributes to the length, while subsequent identical entries are recognized as having prev equal to r and therefore cause a subtraction of the previously added length, effectively counting the word once.

If a word is an empty string, its reversal is also empty. The algorithm treats the empty string as a prefix of any other string, so when it appears before a non-empty word in the sorted order, the subtraction step removes the length previously added for the empty entry, leaving only the length of the non-empty word plus its delimiter. This behavior correctly reflects that an empty word does not increase the encoding size.

The placeholder "STOP" guarantees that the very first word processed will never be merged with a non-existent predecessor, because the comparison r.startswith(prev) will be false for any legitimate lowercase word. This avoids special-case handling for the first iteration.

Performance Optimizations

The reversal of each word is performed using Python’s slice syntax with a step of -1, which is a highly efficient, low-level operation implemented in C. This avoids the overhead of explicit loops or temporary data structures.

Sorting the reversed list leverages the built-in sorted function, which employs Timsort-a hybrid stable sorting algorithm optimized for real-world data patterns. By sorting only once and then scanning linearly, the algorithm minimizes the number of comparisons needed to detect suffix relationships.

The merge check uses a length comparison before invoking startswith. By confirming that prev is not longer than r, the code prevents unnecessary prefix checks that would always fail, reducing the number of string scans in cases where many words have varying lengths.

The accumulator result is updated incrementally, and the subtraction for merged prefixes occurs immediately after the addition. This in-place adjustment eliminates the need for a secondary pass or auxiliary data structures to track which words have been merged, keeping memory usage low and the overall flow straightforward.

Imagine that these words are like colorful blocks that you want to stack neatly on a shelf. Sometimes, the end of one word looks exactly like the start of another word. When that happens, you can push the two words together so they overlap, taking up less space on the shelf. This code starts by turning all the words around backwards, like looking at them in a mirror, so it is easier to see if they share the same beginning. It sorts these backward words into an orderly line. Then, it walks down the line to measure the length of each word. If the code notices that a new word starts with the same letters as the word that came right before it, it realizes they can overlap. It subtracts the extra space that is saved by stacking them together. By the time it finishes looking at all the words, it has calculated the shortest amount of space needed to fit them all on the shelf.

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

not analyzed yet

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			Go
	LeetcodeHelp	C++	Java	Python
	Progiez	C++	Java	Python
github	black-shadows	C++
	charles-wangkai		Java
	fengvyi	C++
	fpdjsns	C++
	gouthampradhan		Java
	halfrost						Go
	haoel	C++
	JoshCrozier					JS
	lkwq007			Python
	ruoru				Rust
	suxrobGM							C#
	trung-hn			Python
	varunu28		Java
	vthwang		Java
	YuriSpiridonov			Python
	zfang399	C++
AlgoMonster	C++, Python, Java, TypeScript
WalkCCC	C++, Python, Java
leetcode.ca	C++, Go, Java, Python
LeetcodeHelp	C++, Java, Python
Progiez	C++, Java, Python
black-shadows	C++, C++
charles-wangkai	Java
fengvyi	C++
fpdjsns	C++
gouthampradhan	Java
halfrost	Go
haoel	C++
JoshCrozier	JavaScript
lkwq007	Python
ruoru	Rust
suxrobGM	C#
trung-hn	Python
varunu28	Java
vthwang	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