Skip to main content

527 - Word Abbreviation

Difficulty: Hard | Pattern: Greedy + Trie | Company tags: Google

Problem Statement​

Given an array of distinct strings words, return the shortest abbreviation for each word such that no two words share the same abbreviation.

An abbreviation of a word is of the form <first letter><number><last letter> where number is the count of omitted letters. If an abbreviation does not make a word shorter, keep the original word.

Example:

Input: words = ["like","god","internal","me","internet","interval","intension","face","intrusion"]
Output: ["l2e","god","internal","me","i6t","interval","inte4n","f2e","intr4n"]

Approach: Greedy Prefix Length — O(n × L²)​

Key insight: Group words by their abbreviation. If multiple words share an abbreviation, increase the prefix length until they're unique.

def wordsAbbreviation(words: list[str]) -> list[str]:
    n = len(words)
    abbrevs = [None] * n
    prefix_len = [1] * n  # start with prefix length 1
    
    def abbrev(word, p):
        if p + 2 >= len(word):
            return word  # abbreviation not shorter
        return word[:p] + str(len(word) - p - 1) + word[-1]
    
    # Generate initial abbreviations
    for i in range(n):
        abbrevs[i] = abbrev(words[i], 1)
    
    # Resolve conflicts
    changed = True
    while changed:
        changed = False
        count = {}
        for a in abbrevs:
            count[a] = count.get(a, 0) + 1
        
        for i in range(n):
            if count[abbrevs[i]] > 1:
                prefix_len[i] += 1
                abbrevs[i] = abbrev(words[i], prefix_len[i])
                changed = True
    
    return abbrevs

Algorithm Flow​

Dry Run​

words = ["internal","interval","intension"]

Initial: all → "i6l","i6l","i6n" (wait, different last chars → different abbrevs) Actually: "internal"→i6l, "interval"→i6l? No: "interval" last char is 'l' too!

  • "internal" (8 chars): i + 6 + l = "i6l"
  • "interval" (8 chars): i + 6 + l = "i6l" → conflict!
  • prefix_len both → 2 → "in5l" vs "in5l" → still conflict!
  • prefix_len → 3 → "int4l" vs "int4l" → still! → 4 → "inte3l" vs "inte3l"... → 5 → "inter2l" → "inter2l" vs "inter2l" until different

Eventually resolved by longer prefixes.

Complexity​

  • Time: O(n × L²) worst case
  • Space: O(n × L)

Key Terms​

TermDefinition
Abbreviation<first letter><count of omitted letters><last letter>, only used if shorter than the original word.
Prefix lengthNumber of leading characters kept unabbreviated; increased incrementally to break ties.
Conflict groupSet of words that currently map to the same abbreviation and must be disambiguated further.
Greedy expansionStrategy of growing the prefix by exactly one character per round only for words still in conflict.
Trie (alternative approach)Groups words on a shared prefix tree so the minimum distinguishing prefix length can be read off node depth/branching instead of repeated regrouping.

FAQ​

Q1: Why can't we just abbreviate every word with the same fixed prefix length? Because different words need different prefix lengths to become unique — a global fixed length either over-abbreviates some words or fails to resolve conflicts in others. The prefix length must be computed per-word.

Q2: What's the actual stopping condition for the while loop? The loop stops when no abbreviation is shared by more than one word (changed stays False for a full pass). At that point every abbreviation is unique.

Q3: How is this related to trie-based solutions? A trie built from all words lets you find, for each word, the shortest prefix at which its path diverges from every other word — this is the same information the greedy loop computes iteratively but in O(n × L) instead of repeated O(n × L) passes, giving O(n × L) overall versus O(n × L²) for the greedy version.

Q4: Why do words length ≤ 3 (or where abbreviation doesn't save length) get skipped? Because the problem defines abbreviation as only valid if it's strictly shorter than the original word; if p + 2 >= len(word), the abbreviation is at least as long as the word, so the original word is kept.

Q5: What's the worst-case input that maximizes runtime? Many words sharing a very long common prefix (e.g., all starting with the same 20 characters) forces the prefix length to grow close to the full word length before conflicts resolve, driving the loop toward its O(n × L²) bound.

Quick Revision​

  • Problem: assign each word the shortest unique <first><count><last> abbreviation.
  • Abbreviation only replaces a word if it's actually shorter.
  • Greedy approach: start all words at prefix length 1, detect abbreviation collisions, bump prefix length only for colliding words, repeat.
  • Termination: loop ends once every abbreviation in the current pass is unique.
  • Time complexity: O(n × L²) for the greedy re-scan approach; O(n × L) achievable with a trie.
  • Space complexity: O(n × L) for storing abbreviations and prefix lengths.
  • Trie alternative: build a trie of all words, track branching count per node, and read off the minimal distinguishing prefix directly.
  • Edge case: words already shorter than or equal to their abbreviation form stay unchanged.
  • Edge case: duplicate words are disallowed by the problem (distinct strings), simplifying collision handling.
  • 820 - Short Encoding of Words — trie-based grouping of words by shared suffixes/prefixes.
  • 745 - Prefix and Suffix Search — trie structure keyed on word prefixes for fast lookup.
  • No explicit "Variants" section existed in this page's original content to cross-link; the pattern (grouping by prefix, incrementally disambiguating) is otherwise closest to trie-based dictionary problems like Word Search II and Implement Trie.