Minimal Unique Word Abbreviations
Company: Apple
Role: Software Engineer
Category: Coding & Algorithms
Difficulty: medium
Interview Round: Onsite
# Minimal Unique Word Abbreviations
You are given an array `words` of `n` **distinct** strings. Produce a **minimal abbreviation** for every word according to the rules below, and return the abbreviations in the **same order** as the input.
## How an abbreviation is formed
An abbreviation of a word uses a **prefix** of the first `k` characters, followed by the **count** of the characters between that prefix and the last character, followed by the **last** character.
For a prefix length `k` (with `1 <= k <= length - 2`):
```
abbr(word, k) = word[0 .. k-1] + (length - k - 1) + word[length - 1]
```
With the smallest prefix `k = 1`, this is: `first character` + `(length - 2)` + `last character`. For example:
- `"apple"` -> `"a3e"` (`a`, then 3 middle characters `ppl`, then `e`)
- `"internationalization"` -> `"i18n"`
## Rules for choosing each word's abbreviation
1. Start every word at `k = 1` (the shortest abbreviation).
2. If an abbreviation is **shared by two or more words**, those conflicting words must use a **longer prefix**: increase `k` for the conflicting words and recompute, repeating until each word's abbreviation is **unique** among all words.
3. If at any point a word's abbreviation is **not shorter** than the original word (its length is `>=` the word's length), use the **original word** itself instead of the abbreviation.
## Examples
- Input: `["dog", "deer", "deal"]`
Output: `["dog", "d2r", "d2l"]`
- `"dog"`: `"d1g"` has length 3, not shorter than `"dog"`, so keep `"dog"`.
- `"deer"` -> `"d2r"`, `"deal"` -> `"d2l"`; these are already unique.
- Input: `["abcdefz", "abxdefz"]`
Output: `["abc3z", "abx3z"]`
- At `k = 1` both become `"a5z"` (conflict); at `k = 2` both become `"ab4z"` (still conflict); at `k = 3` they become `"abc3z"` and `"abx3z"`, which are unique and shorter than the originals.
## Constraints
- `1 <= n <= 400`
- `2 <= words[i].length <= 400`
- All strings in `words` are **distinct** and consist of lowercase English letters.
## Required
Return an array of the minimal abbreviations, in the same order as `words`.
Quick Answer: This question evaluates a candidate's ability to design a string-processing algorithm involving iterative refinement and conflict resolution among grouped elements. It tests string manipulation, hashing for grouping, and careful edge-case handling under length constraints, a common way to assess practical coding proficiency in algorithm interviews.
You are given an array `words` of `n` distinct lowercase strings. Produce a minimal abbreviation for every word and return the abbreviations in the same order as the input.
**Forming an abbreviation.** For a prefix length `k` (1-based), `abbr(word, k) = word[0..k-1] + (length - k - 1) + word[length-1]` — the first `k` characters, then the count of the middle characters, then the last character. With `k = 1`: first character + `(length - 2)` + last character. For example `"apple" -> "a3e"` and `"internationalization" -> "i18n"`.
**Choosing each word's abbreviation.**
1. Start every word at `k = 1` (the shortest abbreviation).
2. If an abbreviation is shared by two or more words, increase `k` for the conflicting words and recompute, repeating until every word's abbreviation is unique among all words.
3. If at any point a word's abbreviation is not shorter than the original word (its length is `>=` the word's length), use the original word itself instead.
Return the array of minimal abbreviations in the same order as `words`.
**Examples**
- `["dog", "deer", "deal"] -> ["dog", "d2r", "d2l"]` ("d1g" is not shorter than "dog", so "dog" is kept).
- `["abcdefz", "abxdefz"] -> ["abc3z", "abx3z"]` (both collide at k=1 "a5z" and k=2 "ab4z", becoming unique at k=3).
**Constraints**
- `1 <= n <= 400`
- `2 <= words[i].length <= 400`
- All strings are distinct and consist of lowercase English letters.
Constraints
- 1 <= n <= 400
- 2 <= words[i].length <= 400
- All strings in words are distinct and consist of lowercase English letters.
- Abbreviations must be returned in the same order as the input.
Examples
Input: (["dog", "deer", "deal"],)
Expected Output: ["dog", "d2r", "d2l"]
Explanation: "d1g" is length 3, not shorter than "dog", so "dog" stays. "deer"->"d2r", "deal"->"d2l" are already unique.
Input: (["abcdefz", "abxdefz"],)
Expected Output: ["abc3z", "abx3z"]
Explanation: Both are "a5z" at k=1 and "ab4z" at k=2 (still colliding); at k=3 they become "abc3z" and "abx3z", unique and shorter.
Hints
- Write a helper abbr(word, k) that builds first-k-chars + middle-count + last-char, and falls back to the original word whenever the candidate is not strictly shorter.
- Start every word at k = 1, then repeatedly find groups of words sharing the same current abbreviation and bump the prefix length k for every word in a colliding group.
- Because all input words are distinct and never contain digits, a full-word fallback can never collide with a digit-containing abbreviation, which guarantees the loop terminates.