# Short Encoding of Words
**Difficulty:** MEDIUM
[External](https://leetcode.com/problems/short-encoding-of-words)
Canonical: https://scaleengineer.com/dsa/problems/short-encoding-of-words
**Data structures:** Array, Hash Table, String, Trie
---
## Problem
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 1:**

**Input:** words = ["time", "me", "bell"]
**Output:** 10
**Explanation:** A valid encoding would be s = `"time#bell#" and indices = [0, 2, 5`].
words[0] = "time", the substring of s starting from indices[0] = 0 to the next '#' is underlined in "time#bell#"
words[1] = "me", the substring of s starting from indices[1] = 2 to the next '#' is underlined in "time#bell#"
words[2] = "bell", the substring of s starting from indices[2] = 5 to the next '#' is underlined in "time#bell#"

**Example 2:**

**Input:** words = ["t"]
**Output:** 2
**Explanation:** A valid encoding would be s = "t#" and indices = [0].

**Constraints:**

* `1 <= words.length <= 2000`
* `1 <= words[i].length <= 7`
* `words[i]` consists of only lowercase letters.

# Approaches
## Set-based Suffix Removal
This approach identifies words that are suffixes of other words and excludes them from the final count. It uses a `Set` to efficiently store the initial words and then iterates through each word, removing any of its suffixes that are also present in the set. The final length is the sum of the lengths of the remaining words plus a '#' for each.
**Time:** O(N * K^2), where N is the number of words and K is the maximum length of a word. For each of the N words, we iterate up to K-1 times to generate suffixes. Each suffix generation (`substring`) and set removal (`remove`) takes O(K) time on average. · **Space:** O(N * K), where N is the number of words and K is the maximum length of a word. This space is used to store the words in the `HashSet`.
**Pros:** Relatively simple to understand and implement.; Correctly handles duplicate words by using a set.
**Cons:** Inefficient due to nested loops and repeated string operations (substring creation).; The time complexity of O(N * K^2) can be too slow for larger inputs where K is not small.
### Explanation
The core idea is that if a word `w1` is a suffix of `w2`, we only need to encode `w2`. The encoding for `w1` is implicitly included. For example, encoding `"time#"` also covers `"me"`.

To implement this, we first add all unique words to a `HashSet`. This handles duplicates and allows for quick removal.

Then, we iterate through each word from the original list. For each word, we generate all its possible proper suffixes (e.g., for `"time"`, the suffixes are `"ime"`, `"me"`, `"e"`). For each generated suffix, we attempt to remove it from our `HashSet`. If the suffix exists in the set, it will be removed.

After checking all words and removing their suffixes, the set will only contain words that are not suffixes of any other word in the original list. These are the words we must include in our reference string. The final length is the sum of the lengths of these remaining words, plus 1 for each '#' delimiter.

```java
import java.util.Arrays;
import java.util.HashSet;
import java.util.Set;

class Solution {
    public int minimumLengthEncoding(String[] words) {
        Set<String> goodWords = new HashSet<>(Arrays.asList(words));
        for (String word : words) {
            // We only need to check for suffixes if the word itself is in the set
            if (goodWords.contains(word)) {
                for (int i = 1; i < word.length(); i++) {
                    String suffix = word.substring(i);
                    goodWords.remove(suffix);
                }
            }
        }

        int totalLength = 0;
        for (String word : goodWords) {
            totalLength += word.length() + 1;
        }
        return totalLength;
    }
}
```
### Algorithm
1. Create a `HashSet` from the input `words` array to store unique words.
2. Iterate through each `word` in the original `words` array.
3. For each `word`, generate all its proper suffixes (substrings starting from index 1).
4. For each generated `suffix`, attempt to remove it from the `HashSet`.
5. After the iteration, the `HashSet` will only contain words that are not suffixes of any other word.
6. Calculate the final length by summing `word.length() + 1` for each word remaining in the set.

## Sorting Reversed Words
This approach transforms the suffix problem into a prefix problem by reversing all words. By sorting the reversed words lexicographically, we can easily check if one word is a prefix of another in a single pass, thus identifying which words are suffixes of others.
**Time:** O(N*K + K * N log N), where N is the number of unique words and K is the maximum length. This is dominated by the sorting step and simplifies to O(K * N log N). · **Space:** O(N * K) to store the unique words and their reversed versions.
**Pros:** More efficient than the brute-force suffix checking, especially when K is large.; Cleverly transforms the problem into a simpler prefix check after sorting.
**Cons:** Requires extra space to store the reversed words.; The sorting step's performance depends on string comparison, which can be costly if K is large.
### Explanation
The key insight is that `word1` is a suffix of `word2` if and only if `reverse(word1)` is a prefix of `reverse(word2)`. For example, `"me"` is a suffix of `"time"`, and `"em"` is a prefix of `"emit"`.

By sorting an array of the reversed words, we group words with common prefixes together. For instance, `"em"` and `"emit"` would be adjacent after sorting.

The algorithm proceeds as follows:
1. First, remove duplicate words using a `Set` to avoid redundant processing.
2. Reverse each unique word.
3. Sort the array of reversed words lexicographically.
4. Iterate through the sorted array. If a word `reversed_words[i]` is a prefix of the next word `reversed_words[i+1]`, it means the original word corresponding to `reversed_words[i]` is a suffix of the original word for `reversed_words[i+1]`. Therefore, we don't need to count it.
5. We only add the length of a word (`word.length() + 1`) to our total if it's *not* a prefix of the next one. The last word in the sorted list is always counted as it cannot be a prefix of any subsequent word.

```java
import java.util.Arrays;
import java.util.HashSet;
import java.util.Set;

class Solution {
    public int minimumLengthEncoding(String[] words) {
        Set<String> uniqueWordsSet = new HashSet<>(Arrays.asList(words));
        String[] uniqueWords = new String[uniqueWordsSet.size()];
        int k = 0;
        for (String word : uniqueWordsSet) {
            uniqueWords[k++] = new StringBuilder(word).reverse().toString();
        }
        
        Arrays.sort(uniqueWords);
        
        int totalLength = 0;
        for (int i = 0; i < uniqueWords.length - 1; i++) {
            if (!uniqueWords[i+1].startsWith(uniqueWords[i])) {
                totalLength += uniqueWords[i].length() + 1;
            }
        }
        
        // Add the length of the last word, if the array is not empty
        if (uniqueWords.length > 0) {
            totalLength += uniqueWords[uniqueWords.length - 1].length() + 1;
        }
        
        return totalLength;
    }
}
```
### Algorithm
1. Create a `Set` of words to handle duplicates.
2. Create a new array by reversing each unique word.
3. Sort the array of reversed words lexicographically.
4. Initialize `totalLength = 0`.
5. Iterate from `i = 0` to `n-2`. If `reversed_words[i+1]` does not start with `reversed_words[i]`, it means the original word is not a suffix of the next, so we add its encoded length (`length + 1`) to `totalLength`.
6. After the loop, add the encoded length of the last word to `totalLength`.
7. Return `totalLength`.

## Trie on Reversed Words
This is the most optimal approach. It uses a Trie (prefix tree) data structure to efficiently handle the prefix relationships among reversed words. By inserting all reversed words into a Trie, the words that need to be encoded correspond to the leaves of the Trie, and their combined length can be found with a single traversal.
**Time:** O(N * K), where N is the number of words and K is the maximum length of a word. Each character of each word is visited once to build the Trie and once during the DFS traversal. · **Space:** O(N * K) in the worst case for the Trie, where each character of each word creates a new node.
**Pros:** Most efficient time complexity at O(N * K).; Scales well with the number of words and their lengths.; Provides a clean and structured way to solve prefix/suffix problems.
**Cons:** More complex to implement compared to other approaches.; Requires understanding of the Trie data structure.
### Explanation
As with the sorting approach, we convert the suffix problem to a prefix problem by reversing the words. A Trie is a perfect data structure for managing and querying prefixes.

We build a Trie and insert each reversed word into it. For example, inserting `"emit"` (reverse of `"time"`) creates a path `e -> m -> i -> t`. When we then insert `"em"` (reverse of `"me"`), we traverse the existing path `e -> m` and do not create new nodes.

The key observation is that if a reversed word `rw1` is a prefix of another reversed word `rw2`, then the path for `rw1` in the Trie will be a prefix of the path for `rw2`. The node where `rw1` ends will not be a leaf node (it will have children).

Therefore, the words that are not suffixes of any other word correspond to the reversed words that are not prefixes of any other reversed word. In the Trie, these are represented by paths ending in leaf nodes (nodes with no children). The length of the shortest encoding is the sum of `(depth of leaf + 1)` for every leaf node.

```java
import java.util.Arrays;
import java.util.HashSet;
import java.util.Set;

class Solution {
    class TrieNode {
        TrieNode[] children = new TrieNode[26];
    }

    public int minimumLengthEncoding(String[] words) {
        Set<String> uniqueWords = new HashSet<>(Arrays.asList(words));
        TrieNode root = new TrieNode();
        
        // Build the Trie with reversed words
        for (String word : uniqueWords) {
            TrieNode current = root;
            for (int i = word.length() - 1; i >= 0; i--) {
                char c = word.charAt(i);
                if (current.children[c - 'a'] == null) {
                    current.children[c - 'a'] = new TrieNode();
                }
                current = current.children[c - 'a'];
            }
        }
        
        // Use DFS to find all leaf nodes and sum their path lengths
        int[] totalLength = {0};
        dfs(root, 1, totalLength);
        return totalLength[0];
    }

    private void dfs(TrieNode node, int depth, int[] totalLength) {
        boolean isLeaf = true;
        for (TrieNode child : node.children) {
            if (child != null) {
                isLeaf = false;
                dfs(child, depth + 1, totalLength);
            }
        }
        
        if (isLeaf && depth > 1) {
            // A leaf node represents a word that is not a suffix of another.
            // The word's length is `depth - 1`.
            // The encoded length is `word_length + 1` which is `(depth - 1) + 1 = depth`.
            totalLength[0] += depth;
        }
    }
}
```
### Algorithm
1. Define a `TrieNode` class.
2. Create a `HashSet` from the input `words` to handle duplicates.
3. Initialize an empty Trie data structure.
4. For each unique word, reverse it and insert it into the Trie.
5. Perform a Depth-First Search (DFS) traversal starting from the Trie's root, keeping track of the current path depth.
6. If a node is a leaf (has no children), it represents a word that is not a suffix of any other. Add its encoded length (`depth`) to a total sum. The word length is `depth - 1`, so `word_length + 1` for the '#' is simply `depth`.
7. Return the total sum after the traversal is complete.

# Solutions
### Java

```java
class Trie { Trie [] children = new Trie [ 26 ]; } class Solution { public int minimumLengthEncoding ( String [] words ) { Trie root = new Trie (); for ( String w : words ) { Trie cur = root ; for ( int i = w . length () - 1 ; i >= 0 ; i --) { int idx = w . charAt ( i ) - 'a' ; if ( cur . children [ idx ] == null ) { cur . children [ idx ] = new Trie (); } cur = cur . children [ idx ]; } } return dfs ( root , 1 ); } private int dfs ( Trie cur , int l ) { boolean isLeaf = true ; int ans = 0 ; for ( int i = 0 ; i < 26 ; i ++) { if ( cur . children [ i ] != null ) { isLeaf = false ; ans += dfs ( cur . children [ i ], l + 1 ); } } if ( isLeaf ) { ans += l ; } return ans ; } }
```

### CPP

```cpp
struct Trie { Trie * children [ 26 ] = { nullptr }; }; class Solution { public: int minimumLengthEncoding ( vector < string >& words ) { auto root = new Trie (); for ( auto & w : words ) { auto cur = root ; for ( int i = w . size () - 1 ; i >= 0 ; -- i ) { if ( cur -> children [ w [ i ] - 'a' ] == nullptr ) { cur -> children [ w [ i ] - 'a' ] = new Trie (); } cur = cur -> children [ w [ i ] - 'a' ]; } } return dfs ( root , 1 ); } private: int dfs ( Trie * cur , int l ) { bool isLeaf = true ; int ans = 0 ; for ( int i = 0 ; i < 26 ; ++ i ) { if ( cur -> children [ i ] != nullptr ) { isLeaf = false ; ans += dfs ( cur -> children [ i ], l + 1 ); } } if ( isLeaf ) { ans += l ; } return ans ; } };
```

### Python

```python
class Trie : def __init__ ( self ) -> None : self . children = [ None ] * 26 class Solution : def minimumLengthEncoding ( self , words : List [ str ]) -> int : root = Trie () for w in words : cur = root for i in range ( len ( w ) - 1 , - 1 , - 1 ): idx = ord ( w [ i ]) - ord ( 'a' ) if cur . children [ idx ] == None : cur . children [ idx ] = Trie () cur = cur . children [ idx ] return self . dfs ( root , 1 ) def dfs ( self , 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
```