Short Encoding of Words — Medium Problem & Solution

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 <= 2000
• 1 <= words[i].length <= 7
• words[i] consists of lowercase English letters.

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

1. Put all words in a set.
2. For each word, remove every proper suffix of it from the set — that is, w[1..], w[2..], and so on.
3. Sum length + 1 over 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 0 deletes 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 + 1 per 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)

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#, C++, Go, Java, Kotlin, PHP, Ruby, Rust, Swift, TypeScript.

More strings problems

• Make Three Strings Equal Medium
• Number of Ways to Divide a Long Corridor Medium
• Maximum Number of Non-overlapping Palindrome Substrings Medium
• Count Number of Texts Medium
• Delete Characters to Make Fancy String Medium
• Count Number of Homogenous Substrings Medium