Word Abbreviation (Unique Abbreviation for Each Word)

Problem: Word Abbreviation Given an array of strings words (lowercase words), generate an abbreviation for each word such that: Abbreviation rule: If the word length is <= 3, the abbreviation is the word itself. Otherwise, the abbreviation format is: first letter + number of omitted middle characters + last letter Example: "international" -> "i11l". Uniqueness requirement: the resulting abbreviations array abbrs must satisfy abbrs[i] != abbrs[j] for any i != j. Minimality requirement: subject to uniqueness, each word’s abbreviation should be as short as possible by: grouping words that collide under the current abbreviation; increasing the prefix length for colliding words until they become unique; if an abbreviation would not be shorter than the original word, return the original word. Return an array abbrs of the same length as words. Input (stdin) First line: integer n, the number of words. Next n lines: one word per line. Output (stdout) Print n lines, each the abbreviation for the corresponding input word (same order). Constraints 1 <= n <= 2 * 10^4 1 <= len(words[i]) <= 200 Words contain only lowercase letters Duplicates may exist in words Examples Input: 6 like god internal me internet interval Output: l2e god intern1l me i6t interv1l Input: 3 abc abcd abcde Output: abc a2d a3e Input: 4 identical identical identity idiotic Output: identical identical i6y i5c Example Input 6 like god internal me internet interval Output l2e god intern1l me i6t interv1l