Short Encoding of Words — Reverse Trie Suffix Deduplication

Problem Statement#

LeetCode 820 — Short Encoding of Words | Difficulty: Medium

A valid encoding of an array words is any reference string s and array of indices indices such that:

• indices.length == words.length
• The encoding of each words[i] can be found by starting at index indices[i] and reading the substring up to (but not including) the next '#' character in s.

Given an array words, return the length of the shortest reference string of any valid encoding.

Example:

Input:  words = ["time","me","bell"]
Output: 10
 
Explanation: The shortest reference is "time#bell#" with indices [0, 2, 5].
  s[0:4] = "time"
  s[2:4] = "me"
  s[5:9] = "bell"
"me" is a suffix of "time", so they share encoding space.

Constraints:

• 1 <= words.length <= 2000
• 1 <= words[i].length <= 7
• words[i] consists of lowercase English letters.

Why This Problem Matters#

Short Encoding of Words is the canonical "reverse trie" problem and a frequent Amazon and Google interview question. It tests three skills at once: recognising that a problem about suffixes should reverse to a problem about prefixes, building a trie of reversed strings, and reading off the answer from leaf nodes only.

The reverse-trie pattern shows up everywhere — DNS records ("indexing by domain" reverses to "indexing by reversed domain"), file path matching, suffix arrays in bioinformatics, and reverse-search autocompletes. Once a candidate sees this trick, the entire family of suffix problems becomes tractable with the same prefix-tree mental model.

The Core Insight#

A word w does not need its own encoding entry if and only if w is a suffix of some other word in the list. In the reference string, w can be read off by starting later inside that other word's encoding.

To detect "is w a suffix of some other word," reverse every word and ask "is reversed(w) a prefix of reversed(otherWord)." Prefix containment is exactly what a trie answers in O(L) per query.

Even better: build a trie of all reversed words. A word contributes len(w) + 1 to the encoding length (the +1 is for #) if and only if its reversed form ends at a leaf of the trie. If it ends at an internal node, some longer reversed word continues through it — meaning the original word is a suffix of that longer word and gets folded into its encoding.

So the answer is: sum of (depth + 1) over all leaf nodes of the reversed-words trie.

Visual Dry Run#

Words: ["time", "me", "bell"]. Reversed: ["emit", "em", "lleb"].

Insert into trie:

root
 |-- e -- m (cnt of words ending here: 1, "me")
 |        |-- i -- t (END "time")
 |
 |-- l -- l -- e -- b (END "bell")

When inserting "em" (reversed "me"), we reach node m and stop — but later "emit" (reversed "time") extends past it, so m is not a leaf.

Leaves of the final trie:

• t at depth 4 → contributes 4 + 1 = 5 (encoding "time#")
• b at depth 4 → contributes 4 + 1 = 5 (encoding "bell#")

Total: 5 + 5 = 10. The node for "em" is internal, so "me" is folded into "time"'s encoding for free.

Solution (Optimal) — Reverse Trie#

Python#

class TrieNode:
    __slots__ = ("children",)
    def __init__(self):
        self.children = {}
 
class Solution:
    def minimumLengthEncoding(self, words: list[str]) -> int:
        # Deduplicate first — identical words contribute only once.
        words = list(set(words))
        root = TrieNode()
        # Map each word's reversed end-node so we can compute leaf depth later.
        ends = []
        for w in words:
            node = root
            for ch in reversed(w):
                if ch not in node.children:
                    node.children[ch] = TrieNode()
                node = node.children[ch]
            ends.append((node, len(w)))
        # A word's end-node is a leaf if it has no children.
        return sum(length + 1 for node, length in ends if not node.children)

JavaScript#

class TrieNode {
  constructor() {
    this.children = {};
  }
}
 
var minimumLengthEncoding = function(words) {
  words = [...new Set(words)];
  const root = new TrieNode();
  const ends = [];
  for (const w of words) {
    let node = root;
    for (let i = w.length - 1; i >= 0; i--) {
      const ch = w[i];
      if (!node.children[ch]) node.children[ch] = new TrieNode();
      node = node.children[ch];
    }
    ends.push([node, w.length]);
  }
  let total = 0;
  for (const [node, len] of ends) {
    if (Object.keys(node.children).length === 0) total += len + 1;
  }
  return total;
};

Complexity#

• Time: O(sum of word lengths) — each character inserted once.
• Space: O(sum of word lengths) for trie nodes plus the ends array.

Common Mistakes#

1. Forgetting to deduplicate — the input can contain duplicate words; without set, you double-count.
2. Inserting words forward instead of reversed — reduces the problem to prefix matching, which does not detect suffix folding.
3. Counting all terminal nodes instead of only leaves — a terminal that has children means a longer word extends through it, so the shorter word is folded in.
4. Off-by-one on the # separator — every contributing word adds len + 1, not just len.
5. Iterating ends as a set instead of preserving multiplicity — fine after dedup, but if you skip dedup and use a set of end-nodes you may miss colliding words.
6. Trying a sort-based solution that compares full pairs — O(N^2 times L) is too slow for the constraints; trie or hash-of-suffixes is the right fit.

Interview Tips#

• Open with the observation: "A word is folded if and only if it is a suffix of another."
• Justify the reversal: "Suffix in the original corresponds to prefix in the reversed string, and tries are built for prefix queries."
• State the leaf-only contribution rule clearly: "Internal nodes mean a longer word extends through; only leaves bring fresh characters into the encoding."
• Mention the alternative O(N times L) hash-set approach — for each word w, for each suffix, remove it from a set. Trie is faster constant factor and more elegant.
• The trie naturally handles the dedup case where "time" appears twice in the list.

Follow-up Questions#

• Reconstruct the actual reference string? DFS from each leaf; concatenate the path-reversed plus #.
• Allow encoding to share boundaries (e.g., overlap #)? Problem becomes a different optimisation; suffix tree or Lyndon decomposition.
• Stream of words arriving online? Trie supports inserts; recompute total leaves incrementally.
• What if alphabet is huge (Unicode)? Replace dict children with hashmap; algorithm is identical.
• Prove minimality? Each leaf must contribute its full length once; any encoding sharing fewer characters than this would lose at least one suffix.

Key Takeaways#

• Reverse trie turns suffix problems into prefix problems — a universal algorithmic trick.
• A word survives the encoding only if its reversed form ends at a leaf of the reversed-words trie.
• Each surviving word contributes len + 1 (the +1 is for the # separator).
• Deduplicate the input upfront — duplicates do not change the answer.
• Time and space are O(sum of word lengths) — optimal for the constraints.
• The reverse-trie pattern reappears in DNS indexing, suffix automatons, and reverse-domain matching at FAANG search infra.