Skip to main content

820 - Short Encoding of Words

Difficulty: Medium | Pattern: Trie / Suffix Hashing | Company tags: Amazon, Google

Problem Statement​

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

  • words.length == indices.length
  • The reference string s ends with the '#' character.
  • For each index indices[i], the substring of s starting from indices[i] and up to (but not including) the next '#' character is equal to words[i].

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

Example:

Input: words = ["time","me","bell"]
Output: 10
Explanation: "time#bell#" — "me" is a suffix of "time"

Approach: Remove Suffixes — O(n × L²)​

Key insight: A word can be encoded as part of another word if it's a suffix of another word. Remove all words that are suffixes of other words. The answer is the sum of remaining lengths + 1 (for #) per word.

def shortestReferenceString(words: list[str]) -> int:
    word_set = set(words)
    
    for word in words:
        for i in range(1, len(word)):
            word_set.discard(word[i:])  # remove all suffixes
    
    return sum(len(w) + 1 for w in word_set)

Dry Run​

words = ["time","me","bell"]

word_set = {"time","me","bell"}

Process "time": discard "ime","me","e" → word_set = {"time","bell"} Process "me": discard "e" → no change Process "bell": discard "ell","ll","l" → no change

Remaining: {"time","bell"} → lengths: 4+1 + 4+1 = 10 ✓

Alternative: Trie on Reversed Words​

Build a trie on reversed words. Leaf nodes are words that aren't suffixes of others.

Complexity​

  • Time: O(n × L²) — for each word, generate all suffixes and look them up
  • Space: O(n × L) for the set