Short Encoding of Words — Solution in Python, Java & C++
Short Encoding of Words solution explained: step-by-step approach, complexity and code in Python, Java, C++ and JavaScript. A medium problem.
Short Encoding of Words is a medium coding problem on strings, hash table and trie, asked in Amazon, Google and Meta interviews.
- Difficulty: Medium
- Topics: Strings, Hash Table, Trie
- Asked at: Amazon, Google, Meta
- Time limit: 2 s
- Memory limit: 256 MB
- Languages: JavaScript, TypeScript, Python, Java, C++, C, C#, Go, Kotlin, Swift, Rust, PHP and Ruby
Problem statement
A valid encoding of words is a reference string s ending in '#' together with one starting index per word, such that reading from that index up to the next '#' spells the word.
For example words = ["time","me","bell"] can be encoded as s = "time#bell#" with indices 0, 2 and 5.
Return the length of the shortest possible reference string.
Example 1
Input: words = ["time","me","bell"]
Output: 10
Explanation: "time#bell#" has length 10 — "me" rides along inside "time#".
Example 2
Input: words = ["t"]
Output: 2
Explanation: "t#".
Example 3
Input: words = ["code","kairo","ro"]
Output: 11
Explanation: "code#kairo#" is 11 characters; "ro" is a suffix of "kairo".
Constraints
1 <= words.length <= 20001 <= words[i].length <= 7words[i] consists of lowercase English letters.
Hints for Short Encoding of Words
Hint 1
A word only saves space when it is a suffix of another word — then it shares that word's ending.
Hint 2
So discard every word that is a proper suffix of some other word.
Hint 3
Each survivor costs its own length plus one for the
'#'.
How to solve Short Encoding of Words
Two words can share encoding space only when one is a suffix of the other, because every word must run up to a '#'. So the shortest encoding keeps exactly the words that are not proper suffixes of any other, and each costs its length plus one.
Approach
- Put all words in a set.
- For each word, remove every proper suffix of it from the set — that is,
w[1..],w[2..], and so on. - Sum
length + 1over the words still in the set.
Why it works
If a is a suffix of b, then a can be read starting inside b's block and costs nothing extra. If neither is a suffix of the other, their blocks cannot overlap at all, since an overlap would force one to end where the other does. So the survivors are exactly the blocks that must be written.
Complexity
- Time —
O(total characters × max word length) - Space —
O(total characters)
Pitfalls
- Starting the suffix loop at
0deletes the word itself and empties the set. - Duplicate words must collapse — a set handles that for free, a list does not.
- The trailing
'#'is part of every block, hence the+ 1per survivor.
Reference solution
Python
from typing import List
def minimumLengthEncoding(words: List[str]) -> int:
keep = set(words)
for w in list(keep):
for i in range(1, len(w)):
keep.discard(w[i:])
return sum(len(w) + 1 for w in keep)Java
public static int minimumLengthEncoding(String[] words) {
Set<String> keep = new HashSet<>(Arrays.asList(words));
for (String w : words) {
for (int i = 1; i < w.length(); i++) keep.remove(w.substring(i));
}
int total = 0;
for (String w : keep) total += w.length() + 1;
return total;
}C++
int minimumLengthEncoding(vector<string>& words) {
unordered_set<string> keep(words.begin(), words.end());
for (const string& w : words) {
for (size_t i = 1; i < w.size(); i++) keep.erase(w.substr(i));
}
int total = 0;
for (const string& w : keep) total += (int) w.size() + 1;
return total;
}JavaScript
var minimumLengthEncoding = function(words) {
var keep = {};
for (var i = 0; i < words.length; i++) keep[words[i]] = true;
for (var j = 0; j < words.length; j++) {
var w = words[j];
for (var k = 1; k < w.length; k++) delete keep[w.substr(k)];
}
var total = 0;
var left = Object.keys(keep);
for (var m = 0; m < left.length; m++) total += left[m].length + 1;
return total;
};Also on the editorial tab: C, C#, Go, Kotlin, PHP, Ruby, Rust, Swift, TypeScript.
All 515 strings problems · the whole catalogue
Learn the technique: Strings · Hashing: Hash Maps and Hash Sets