Short Encoding of Words
Medium · Tries · Array · Hash Table · String · Trie
Problem
A valid encoding of an array words is a reference string s together with an array of indices indices such that:
- len(words) == len(indices),
- s ends with the character '#', and
- for each i, the part of s that starts at indices[i] and ends just before the next '#' equals words[i].
Return the length of the shortest possible reference string s.
For example, words = ["time", "me", "bell"] can be encoded as s = "time#bell#" with indices = [0, 2, 5]: "me" is read from inside "time#".
Examples
Input: words = ["bell","ell","ring"] Output: 10
"ell" is the end of "bell", so s = "bell#ring#" with indices [0, 1, 5]: length 10.
Input: words = ["ab","ab"] Output: 3
Both copies point at "ab#".
Input: words = ["xy","z"] Output: 5
Neither word ends the other: "xy#z#".
Constraints
- 1 <= len(words) <= 2000
- 1 <= len(words[i]) <= 7
- words[i] consists of lowercase letters only
Approaches
- Baseline: test every pair with endswith — time O(n² · L), space O(n)
Follow-up
If words could share beginnings instead of endings, the same trie works without reversing. And if you need the string itself, keep the uncovered words and join them. Both are use cases below.
Related problems
Start free on Cariara · Coding problems · System design studio
