Problem Description

You need to find the shortest possible encoding string that can represent all words in a given array.

The encoding works as follows:

• You create a reference string s that contains all the encoded words separated by # characters
• Each word in the original array is represented by a starting index in this reference string
• Reading from each index until the next # character gives you the corresponding word

For example, if you have words ["time", "me", "bell"], one valid encoding could be:

• Reference string: "time#bell#"
• Indices: [0, 2, 5]
• Reading from index 0 to the first # gives "time"
• Reading from index 2 to the first # gives "me" (which is a suffix of "time")
• Reading from index 5 to the next # gives "bell"

The key insight is that if one word is a suffix of another word, they can share the same encoding space. In the example above, "me" is a suffix of "time", so we don't need a separate "me#" in our encoding.

The solution uses a Trie (prefix tree) built with reversed words to identify which words are suffixes of others:

1. Insert all words into the Trie in reverse order (so suffixes become prefixes)
2. Traverse the Trie using DFS to find all leaf nodes
3. Only leaf nodes represent words that need their own encoding (they're not suffixes of any other word)
4. Sum up the lengths of all paths to leaf nodes, adding 1 for each # character

The function returns the minimum total length of the reference string s needed to encode all words.

Intuition

The key observation is that we want to share as much encoding space as possible between words. When can two words share the same encoding? When one word is a suffix of another.

Think about it this way: if we have "time" and "me", we can encode them as "time#" with indices [0, 2]. The word "me" doesn't need its own separate encoding because it's already contained within "time" as a suffix.

This naturally leads us to think about suffix relationships. How can we efficiently determine which words are suffixes of others? If we reverse all the words, suffix relationships become prefix relationships. For example:

• "time" reversed becomes "emit"
• "me" reversed becomes "em"
• Now "em" is a prefix of "emit"

Prefix relationships are perfectly handled by a Trie data structure! When we insert reversed words into a Trie:

• Words that share prefixes will share paths in the Trie
• A word that is a complete prefix of another (originally a suffix) won't be a leaf node
• Only leaf nodes represent words that need their own encoding

For example, with ["time", "me"]:

• Insert "emit" and "em" into the Trie
• "em" is not a leaf (since "emit" extends beyond it)
• Only "emit" is at a leaf, so only "time#" is needed in the encoding

The final step is calculating the encoding length. We traverse the Trie with DFS, and for each leaf node we encounter, we add the path length plus 1 (for the # character). This gives us the minimum encoding length because we've maximally shared encoding space between words with suffix relationships.

Learn more about Trie patterns.

Solution Approach

The implementation uses a Trie data structure to identify suffix relationships by working with reversed words.

Step 1: Build the Trie with Reversed Words

First, we create a Trie class with an array of 26 children (for each lowercase letter):

class Trie:
    def __init__(self):
        self.children = [None] * 26

Then we insert each word in reverse order into the Trie:

root = Trie()
for w in words:
    cur = root
    for c in w[::-1]:  # Reverse the word
        idx = ord(c) - ord("a")  # Get character index (0-25)
        if cur.children[idx] == None:
            cur.children[idx] = Trie()
        cur = cur.children[idx]

For example, with words ["time", "me", "bell"]:

• "time" becomes "emit" and creates path: root → e → m → i → t
• "me" becomes "em" and follows existing path: root → e → m
• "bell" becomes "lleb" and creates path: root → l → l → e → b

Step 2: Calculate Minimum Encoding Length with DFS

We traverse the Trie using depth-first search to find all leaf nodes:

def dfs(cur: Trie, l: int) -> int:
    isLeaf, ans = True, 0
    for i in range(26):
        if cur.children[i] != None:
            isLeaf = False
            ans += self.dfs(cur.children[i], l + 1)
    if isLeaf:
        ans += l
    return ans

The DFS works as follows:

• Start from the root with length 1
• For each node, check all 26 possible children
• If a node has children, it's not a leaf - recursively explore children with incremented length
• If a node is a leaf (no children), add its path length to the answer
• The path length includes the # character that will follow the word

In our example:

• The path to "t" (from "emit") has length 5, contributing 5 to the answer
• The path to "m" (from "em") is not a leaf, contributing 0
• The path to "b" (from "lleb") has length 5, contributing 5 to the answer
• Total: 5 + 5 = 10, representing "time#bell#"

The algorithm correctly identifies that "me" doesn't need separate encoding since it's a suffix of "time", resulting in the minimum encoding length.

Example Walkthrough

Let's walk through the solution with the example words = ["time", "me", "bell"].

Step 1: Build the Trie with reversed words

We reverse each word and insert it into the Trie:

• "time" → "emit"
• "me" → "em"
• "bell" → "lleb"

Building the Trie:

1. Insert "emit": Creates path root → e → m → i → t
2. Insert "em": Follows existing path root → e → m (no new nodes created!)
3. Insert "lleb": Creates new path root → l → l → e → b

The Trie structure looks like:

       root
      /    \
     e      l
     |      |
     m      l
     |      |
     i      e
     |      |
     t      b

Step 2: DFS traversal to find leaf nodes

Starting DFS from root with initial length 1:

1. From root, explore child 'e':

   • From 'e', explore child 'm':
     • From 'm', explore child 'i':
       • From 'i', explore child 't':
         • 't' is a leaf node! Add length 5 to answer
   • 'm' is not a leaf (has child 'i'), so contributes 0

2. From root, explore child 'l':

   • From 'l', explore child 'l':
     • From second 'l', explore child 'e':
       • From 'e', explore child 'b':
         • 'b' is a leaf node! Add length 5 to answer

Step 3: Calculate result

Total encoding length = 5 (for "time#") + 5 (for "bell#") = 10

The minimum encoding string is "time#bell#" with:

• Indices [0, 2, 5]
• "time" starts at index 0
• "me" starts at index 2 (suffix of "time")
• "bell" starts at index 5

Notice how "me" doesn't need its own encoding because it's already contained within "time" as a suffix. This is exactly what our algorithm detected when "em" didn't create a leaf node in the Trie!

Solution Implementation

Time and Space Complexity

Time Complexity: O(N * M)

• Building the Trie: We iterate through all N words, and for each word, we iterate through all its characters (average length M). For each character, we perform constant time operations (checking if child exists, creating new node, moving pointer). This gives us O(N * M) for Trie construction.
• DFS traversal: We visit each node in the Trie exactly once. In the worst case, the Trie contains O(N * M) nodes (when all words are completely different). For each node, we check all 26 children (constant time). Therefore, DFS takes O(N * M).
• Overall time complexity: O(N * M) + O(N * M) = O(N * M)

Space Complexity: O(N * M)

• Trie storage: In the worst case, when all words share no common suffixes (since we're inserting reversed words), we need to store all characters from all words. Each Trie node contains an array of 26 pointers. Maximum nodes needed is O(N * M).
• DFS recursion stack: The maximum depth of recursion equals the length of the longest word, which is at most M. This contributes O(M) to space complexity.
• Overall space complexity: O(N * M) + O(M) = O(N * M)

where N is the number of words and M is the average/maximum length of the words.

Learn more about how to find time and space complexity quickly.

Common Pitfalls

1. Not Handling Duplicate Words

A common mistake is assuming all words in the input array are unique. If duplicates exist, inserting the same word multiple times into the Trie doesn't create additional paths, but naive implementations might count them separately or handle them incorrectly.

Example Problem:

words = ["time", "me", "time"]  # "time" appears twice

Solution: Use a set to remove duplicates before processing:

def minimumLengthEncoding(self, words: List[str]) -> int:
    # Remove duplicates first
    words = list(set(words))
    root = Trie()
    # Continue with the rest of the implementation...

2. Incorrect Initial Depth Value

Starting the DFS with depth 0 instead of 1 is a frequent error. The depth should start at 1 because each word in the encoding needs a '#' separator after it.

Wrong:

return self.dfs(root, 0)  # Incorrect - misses the '#' character

Correct:

return self.dfs(root, 1)  # Correct - accounts for '#' separator

3. Building Regular Trie Instead of Suffix Trie

Attempting to solve this problem with a regular (forward) Trie is a conceptual error. The problem requires identifying suffix relationships, which becomes prefix relationships when words are reversed.

Wrong Approach:

# Inserting words forward - WRONG
for word in words:
    current = root
    for char in word:  # Should be word[::-1]
        # This won't identify suffix relationships correctly

Correct Approach:

# Insert reversed words to identify suffixes
for word in words:
    current = root
    for char in word[::-1]:  # Reverse the word
        # Now suffixes become prefixes in the Trie

4. Memory Optimization Overlooked

Creating a full 26-element array for each Trie node can be wasteful if the input contains words with limited character variety. For large datasets with sparse character usage, this approach uses unnecessary memory.

Alternative Solution Using Dictionary:

class Trie:
    def __init__(self):
        self.children = {}  # Use dictionary instead of array
      
# In the insertion logic:
for char in word[::-1]:
    if char not in current_node.children:
        current_node.children[char] = Trie()
    current_node = current_node.children[char]

# In the DFS logic:
for child in current_node.children.values():
    is_leaf = False
    total_length += self.dfs(child, depth + 1)

5. Not Considering Edge Cases

Failing to handle edge cases like empty arrays or single-character words.

Edge Cases to Consider:

# Empty array
words = []  # Should return 0

# Single character words
words = ["a", "b", "a"]  # Should return 4 ("a#b#")

# All words are suffixes of one word
words = ["me", "time", "ime"]  # Should return 5 ("time#")