Short Encoding of Words solution and explanation
9 more videos on this problem
Short Encoding of Words | Live Coding with Explanation | Leetcode - 820Algorithms Made Easy · 17:27 · 4K views
Leetcode 820. Short Encoding of Words || code + explanation with exampleCode with Alisha · 8:42 · 2K views
Short Encoding of Words | leetcode 820 | Sets | Live coding session 💯💯Coding Decoded · 11:50 · 1K views
Leetcode - Short Encoding of Words (Python)Timothy H Chang · 13:17 · 969 views
Daily Leetcode #340: Mar 06, 2021 - 820. Short Encoding of WordsProgramming Live with Larry · 11:31 · 518 views
Daily Leetcode #811: Jun 20, 2022 - 820. Short Encoding of WordsProgramming Live with Larry · 13:03 · 515 views
820. Short Encoding of Words | Leetcode | City Coder | 6th MarchCity Coder · 6:20 · 230 views
Short Encoding of words || Leetcode medium #820Digital Interview · 9:05 · 168 views
Short Encoding of Words | LeetCode 820 | Coders CampCoders Camp · 8:08 · 159 views
Short Encoding of Words | C++🔥| LeetCode Solution 820Gantavya Malviya · 9:48 · 133 views
The 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
sends with the'#'character. - For each index
indices[i], the substring ofsstarting fromindices[i]and up to (but not including) the next'#'character is equal towords[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 <= 20001 <= words[i].length <= 7words[i]consists of only lowercase letters.
Approach overview
Problem Overview: You are given a list of words and must encode them into a single reference string where each word appears as a suffix ending with #. The goal is to minimize the total length of this encoded string by reusing suffixes whenever possible.
Approach 1: Reverse Sorting and Hash Set (O(total characters) time, O(total characters) space)
The key observation: if a word is a suffix of another word, it does not need its own encoding in the final string. For example, time already covers me. Start by inserting all words into a set for fast lookups. Then iterate through each word and remove all of its suffixes (e.g., word[i:]) from the set. After processing every word, only the words that are not suffixes of any other remain. The final encoded length is the sum of len(word) + 1 for each remaining word to account for the trailing #. This approach relies heavily on constant-time membership checks provided by a hash table and simple substring iteration on each string. It’s concise, efficient, and usually the preferred interview solution.
Approach 2: Suffix Trie (O(total characters) time, O(total characters) space)
A more structured solution builds a Trie using reversed words. Reverse every word so suffix relationships become prefix relationships, then insert characters into a Trie. Each path represents shared suffixes between words. When a word finishes at a leaf node (a node with no children added after insertion), that word contributes len(word) + 1 to the final encoding length. Words that end at internal nodes are suffixes of longer words and do not increase the encoding size. This method explicitly models suffix sharing and avoids repeated substring checks. It’s particularly useful when practicing Trie design or when problems require explicit prefix/suffix structure handling.
Recommended for interviews: The reverse sorting + set approach is typically expected in interviews because it’s short and leverages a clear suffix insight. It demonstrates strong understanding of array iteration and hash-based pruning. The Trie solution is equally optimal in complexity but more verbose; it’s valuable when the interviewer wants to see knowledge of Trie construction and suffix transformations.
Approach 1: Using Suffix Trie
This approach involves building a trie that can be used to efficiently check if one word is a suffix of another. By storing only the unique paths in the trie, the encoding length can be minimized by pointing out the redundancies where one word is a suffix of another.
class TrieNode:
def __init__(self):
self.children = {}
class Solution:
def minimumLengthEncoding(self, words: List[str]) -> int:
# Use only unique words
words = set(words)
# Reverse sort words by length
words = sorted(words, key=lambda x: len(x), reverse=True)
root = TrieNode()
length = 0
for word in words:
current = root
isNew = False
# Insert word into the trie
for char in reversed(word):
if char not in current.children:
isNew = True
current.children[char] = TrieNode()
current = current.children[char]
# If it's a new path in trie, increase length
if isNew:
length += len(word) + 1
return lengthimport java.util.*;
class TrieNode {
Map<Character, TrieNode> children = new HashMap<>();
}
class Solution {
public int minimumLengthEncoding(String[] words) {
TrieNode root = new TrieNode();
Set<TrieNode> leaves = new HashSet<>();
for (String word : words) {
TrieNode node = root;
for (int i = word.length() - 1; i >= 0; i--) {
node = node.children.computeIfAbsent(word.charAt(i), k -> new TrieNode());
}
leaves.add(node);
}
int length = 0;
for (TrieNode leaf : leaves) {
if (leaf.children.isEmpty()) {
length += word.length() + 1;
}
}
return length;
}
}#include <iostream>
#include <vector>
#include <algorithm>
#include <unordered_set>
using namespace std;
struct TrieNode {
unordered_map<char, TrieNode*> children;
};
class Solution {
public:
int minimumLengthEncoding(vector<string>& words) {
TrieNode* root = new TrieNode();
unordered_set<TrieNode*> leaves;
for (auto& word : words) {
TrieNode* node = root;
for (int i = word.size() - 1; i >= 0; --i) {
if (!node->children.count(word[i])) {
node->children[word[i]] = new TrieNode();
}
node = node->children[word[i]];
}
leaves.insert(node);
}
int length = 0;
for (auto& leaf : leaves) {
if (leaf->children.empty()) {
length += word.length() + 1;
}
}
return length;
}
};class TrieNode {
constructor() {
this.children = {};
}
}
var minimumLengthEncoding = function(words) {
let root = new TrieNode();
let leaves = new Set();
for (let word of words) {
let node = root;
for (let i = word.length - 1; i >= 0; i--) {
let char = word[i];
if (!node.children[char]) {
node.children[char] = new TrieNode();
}
node = node.children[char];
}
leaves.add(node);
}
let length = 0;
for (let leaf of leaves) {
if (Object.keys(leaf.children).length === 0) {
length += word.length + 1;
}
}
return length;
};using System;
using System.Collections.Generic;
class TrieNode {
public Dictionary<char, TrieNode> children = new Dictionary<char, TrieNode>();
}
class Solution {
public int MinimumLengthEncoding(string[] words) {
TrieNode root = new TrieNode();
HashSet<TrieNode> leaves = new HashSet<TrieNode>();
foreach (string word in words) {
TrieNode node = root;
for (int i = word.Length - 1; i >= 0; i--) {
if (!node.children.ContainsKey(word[i])) {
node.children[word[i]] = new TrieNode();
}
node = node.children[word[i]];
}
leaves.Add(node);
}
int length = 0;
foreach (TrieNode leaf in leaves) {
if (leaf.children.Count == 0) {
length += word.Length + 1;
}
}
return length;
}
}This solution uses a Trie (prefix tree) to store words in reversed order. It checks whether inserting a word introduces new paths in the Trie, indicating that it isn't a suffix of any word already added. For every new path, the length increases by the length of the word plus one for the '#'.
Time Complexity: O(N * K) where N is the number of words and K is the average length of a word.
Space Complexity: O(N * K) due to the storage in the Trie.
Approach 2: Reverse Sorting and Set
By reverse sorting the words and checking suffix existence, it's possible to efficiently determine the redundant entries. This alternative approach utilizes set operations to ascertain unique encodings, optimizing storage by including only necessary components.
class Solution:
def minimumLengthEncoding(self, words: List[str]) -> int:
words = sorted(set(words), key=lambda w: w[::-1])
unique_words = set(words)
for word in words:
for k in range(1, len(word)):
unique_words.discard(word[k:])
return sum(len(word) + 1 for word in unique_words)import java.util.*;
class Solution {
public int minimumLengthEncoding(String[] words) {
Set<String> uniqueWords = new HashSet<>(Arrays.asList(words));
List<String> sortedWords = new ArrayList<>(uniqueWords);
Collections.sort(sortedWords, (a, b) -> b.compareTo(a));
for (String word : sortedWords) {
for (int i = 1; i < word.length(); i++) {
uniqueWords.remove(word.substring(i));
}
}
int length = 0;
for (String word : uniqueWords) {
length += word.length() + 1;
}
return length;
}
}#include <set>
#include <vector>
#include <string>
#include <algorithm>
using namespace std;
class Solution {
public:
int minimumLengthEncoding(vector<string>& words) {
set<string> unique_words(words.begin(), words.end());
vector<string> sorted_words;
for (auto& word : unique_words) {
sorted_words.push_back(word);
}
sort(sorted_words.begin(), sorted_words.end(), [](const string& a, const string& b){
return a > b;
});
for (auto& word : sorted_words) {
for (size_t i = 1; i < word.size(); ++i) {
unique_words.erase(word.substr(i));
}
}
int length = 0;
for (auto& word : unique_words) {
length += word.size() + 1;
}
return length;
}
};var minimumLengthEncoding = function(words) {
let uniqueWords = new Set(words);
Array.from(uniqueWords).sort().forEach(word => {
for (let i = 1; i < word.length; i++) {
uniqueWords.delete(word.substring(i));
}
});
let length = 0;
uniqueWords.forEach(word => {
length += word.length + 1;
});
return length;
};using System;
using System.Collections.Generic;
class Solution {
public int MinimumLengthEncoding(string[] words) {
HashSet<string> uniqueWords = new HashSet<string>(words);
List<string> sortedWords = new List<string>(uniqueWords);
sortedWords.Sort((a, b) => string.Compare(b, a, StringComparison.Ordinal));
foreach (string word in sortedWords) {
for (int i = 1; i < word.Length; i++) {
uniqueWords.Remove(word.Substring(i));
}
}
int length = 0;
foreach (string word in uniqueWords) {
length += word.Length + 1;
}
return length;
}
}This method sorts the words by reversed string, facilitating checks for suffixes as subsequent entries. By discarding suffixes and iterating over the unique words, it computes the total length effectively.
Time Complexity: O(N * K^2), Space Complexity: O(N * K).
Approach 3: Default Approach
type trie struct {
children [26]*trie
}
func minimumLengthEncoding(words []string) int {
root := new(trie)
for _, w := range words {
cur := root
for i := len(w) - 1; i >= 0; i-- {
if cur.children[w[i]-'a'] == nil {
cur.children[w[i]-'a'] = new(trie)
}
cur = cur.children[w[i]-'a']
}
}
return dfs(root, 1)
}
func dfs(cur *trie, l int) int {
isLeaf, ans := true, 0
for i := 0; i < 26; i++ {
if cur.children[i] != nil {
isLeaf = false
ans += dfs(cur.children[i], l+1)
}
}
if isLeaf {
ans += l
}
return ans
}Complexity comparison
| Approach | Complexity |
|---|---|
| Using Suffix Trie | Time Complexity: O(N * K) where N is the number of words and K is the average length of a word. |
| Reverse Sorting and Set | Time Complexity: O(N * K^2), Space Complexity: O(N * K). |
| Default Approach | – |
Complexity analysis
| Approach | Time | Space | When to Use |
|---|---|---|---|
| Reverse Sorting + Hash Set | O(total characters) | O(total characters) | Best general solution. Simple implementation with hash lookups and suffix removal. |
| Suffix Trie (reversed words) | O(total characters) | O(total characters) | Useful when practicing Trie data structures or when explicit suffix sharing needs to be modeled. |
Frequently asked questions
Is Short Encoding of Words easy or hard?
Short Encoding of Words is rated Medium because the key insight about suffix reuse is not immediately obvious. Once you recognize that suffix words can be removed, the remaining implementation using a set or Trie becomes straightforward.
Short Encoding of Words Python/Java solution
Most implementations either use a hash set to remove suffixes or build a reversed Trie. Both approaches translate cleanly into Python, Java, C++, C#, and JavaScript since they rely on basic string iteration, hash sets, and simple tree nodes.
How to solve Short Encoding of Words in O(n)?
Treat the total number of characters across all words as n. Insert all words into a hash set and remove every suffix of each word starting from index 1. After pruning, sum len(word) + 1 for the remaining words. Each suffix removal and lookup is O(1) average, giving O(n) total processing.
What is the best approach for Short Encoding of Words?
The reverse sorting and hash set approach is the most common solution. Insert all words into a set, then remove every suffix of each word. Only words that are not suffixes remain, and the answer is the sum of their lengths plus one for the '#' delimiter. This runs in O(total characters) time with O(total characters) space.
Is Short Encoding of Words asked at Google/Amazon/Meta?
Suffix and Trie-based string compression problems like this appear in interviews at companies such as Amazon, Google, and Meta. Interviewers use it to evaluate understanding of suffix relationships, hash-based pruning, and Trie data structures.
What data structure is used in Short Encoding of Words?
Two main structures appear in solutions: a hash set for quickly removing suffixes and a Trie for modeling shared suffix paths. The Trie version stores reversed words so suffixes become prefixes during insertion.
What is the time complexity of Short Encoding of Words?
The optimal solutions run in O(total characters) time where total characters is the sum of lengths of all words. Both the suffix Trie and the hash set suffix-removal approach process each character a constant number of times. Space complexity is also O(total characters).