Word Abbreviation

Word Abbreviation is a greedy grouping problem. Each word collapses to a short abbreviation, but two words may produce the same abbreviation — so we keep growing the kept prefix, only for the words that clash, until every abbreviation is unique.

The slow way first

You could compare every pair of words and, whenever two abbreviations match, lengthen both prefixes. But comparing all pairs on every round is wasteful. The real observation is sharper: two abbreviations can only collide if the words already share the same first character, same last character, and same length. Everything else is automatically distinct.

The idea: group, then grow

Start every word at prefix length 1. Then repeat: bucket the words by their current abbreviation. Any bucket with a single word is finished. For every bucket that still has more than one word, grow each of those words' prefix by one character and recompute their abbreviations. Repeat until no bucket has a collision.

Because only the words that still clash grow, each word stops the instant its abbreviation is unique. That greedy stop is what makes the abbreviations minimal.

Walk through it

Step through the animation. like is alone in its group, so its short form l2e is final immediately. internal and interval both start as i6l — a collision. They agree through inter, then differ at n versus v, so growing the prefix to 6 characters yields intern1l and interv1l, which are distinct.

Pseudocode

for each word: abbr = first char + (len - 2) + last char, prefix = 1
repeat:
    bucket the words by their current abbreviation
    if every bucket holds exactly one word: stop
    for each bucket with more than one word:
        for each word in it: prefix += 1, recompute its abbreviation
return the abbreviations

The Python solution

def word_abbr(word, k):
    if len(word) - k <= 3:
        return word
    return word[:k] + str(len(word) - k - 1) + word[-1]
 
def abbreviate(words):
    ans = [word_abbr(w, 1) for w in words]
    prefix = [1] * len(words)
    while True:
        groups = collections.defaultdict(list)
        for i, a in enumerate(ans):
            groups[a].append(i)
        if all(len(g) == 1 for g in groups.values()):
            return ans
        for g in groups.values():
            if len(g) > 1:
                for i in g:
                    prefix[i] += 1
                    ans[i] = word_abbr(words[i], prefix[i])

• word_abbr(word, k) keeps k leading characters, then the count of skipped middle characters, then the last character. If that is not shorter than the word, it returns the word unchanged.
• We seed every word with prefix = 1 and its length-1 abbreviation.
• Each pass buckets indices by their current abbreviation into groups.
• If every bucket has exactly one word, all abbreviations are unique and we return.
• Otherwise, for each colliding bucket we bump that word's prefix and recompute only those abbreviations, then loop again.

Complexity

The prefix of any word can grow at most to the word length, so the number of rounds is bounded by L. Each round touches every word once, giving O(n · L²) overall.

When this pattern shows up

Practice