Problem

Given an array of distinct strings words, return the minimal possibleabbreviations for every word.

The following are the rules for a string abbreviation:

  1. The initial abbreviation for each word is: the first character, then the number of characters in between, followed by the last character.
  2. If more than one word shares the same abbreviation, then perform the following operation:
    • Increase the prefix (characters in the first part) of each of their abbreviations by 1.
      • For example, say you start with the words ["abcdef","abndef"] both initially abbreviated as "a4f". Then, a sequence of operations would be ["a4f","a4f"] -> ["ab3f","ab3f"] -> ["abc2f","abn2f"].
    • This operation is repeated until every abbreviation is unique.
  3. At the end, if an abbreviation did not make a word shorter, then keep it as the original word.

Examples

Example 1:

1
2

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

Example 2:

1
2

Input: words = ["aa","aaa"]
Output: ["aa","aaa"]

Constraints:

  • 1 <= words.length <= 400
  • 2 <= words[i].length <= 400
  • words[i] consists of lowercase English letters.
  • All the strings of words are unique.

Solution

Method 1 – Greedy with Prefix Grouping

Intuition

We want the shortest unique abbreviation for each word. Start with the minimal abbreviation (first letter + count + last letter). If abbreviations collide, increase the prefix length for those words and repeat until all are unique. If the abbreviation is not shorter than the word, use the word itself.

Approach

  1. For each word, start with prefix length 1.
  2. Generate abbreviation: prefix + (len - prefix - 1) + last letter.
  3. Group words by abbreviation. If a group has more than one word, increase their prefix length by 1 and repeat.
  4. When all abbreviations are unique, check if abbreviation is shorter than the word; otherwise, use the word.

Code

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32

#include <unordered_map>
class Solution {
public:
    vector<string> wordsAbbreviation(vector<string>& words) {
        int n = words.size();
        vector<int> pre(n, 1);
        vector<string> ans(n);
        while (true) {
            unordered_map<string, vector<int>> groups;
            for (int i = 0; i < n; ++i) {
                ans[i] = abbr(words[i], pre[i]);
                groups[ans[i]].push_back(i);
            }
            bool unique = true;
            for (auto& [k, v] : groups) {
                if (v.size() > 1) {
                    unique = false;
                    for (int idx : v) pre[idx]++;
                }
            }
            if (unique) break;
        }
        for (int i = 0; i < n; ++i) {
            if (ans[i].size() >= words[i].size()) ans[i] = words[i];
        }
        return ans;
    }
    string abbr(const string& w, int p) {
        if (w.size() - p <= 2) return w;
        return w.substr(0, p) + to_string(w.size() - p - 1) + w.back();
    }
};
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39

func wordsAbbreviation(words []string) []string {
    n := len(words)
    pre := make([]int, n)
    for i := range pre {
        pre[i] = 1
    }
    ans := make([]string, n)
    abbr := func(w string, p int) string {
        if len(w)-p <= 2 {
            return w
        }
        return w[:p] + strconv.Itoa(len(w)-p-1) + w[len(w)-1:]
    }
    for {
        groups := map[string][]int{}
        for i := 0; i < n; i++ {
            ans[i] = abbr(words[i], pre[i])
            groups[ans[i]] = append(groups[ans[i]], i)
        }
        unique := true
        for _, v := range groups {
            if len(v) > 1 {
                unique = false
                for _, idx := range v {
                    pre[idx]++
                }
            }
        }
        if unique {
            break
        }
    }
    for i := 0; i < n; i++ {
        if len(ans[i]) >= len(words[i]) {
            ans[i] = words[i]
        }
    }
    return ans
}
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32

import java.util.*;
class Solution {
    public List<String> wordsAbbreviation(List<String> words) {
        int n = words.size();
        int[] pre = new int[n];
        Arrays.fill(pre, 1);
        String[] ans = new String[n];
        while (true) {
            Map<String, List<Integer>> groups = new HashMap<>();
            for (int i = 0; i < n; i++) {
                ans[i] = abbr(words.get(i), pre[i]);
                groups.computeIfAbsent(ans[i], k -> new ArrayList<>()).add(i);
            }
            boolean unique = true;
            for (List<Integer> v : groups.values()) {
                if (v.size() > 1) {
                    unique = false;
                    for (int idx : v) pre[idx]++;
                }
            }
            if (unique) break;
        }
        for (int i = 0; i < n; i++) {
            if (ans[i].length() >= words.get(i).length()) ans[i] = words.get(i);
        }
        return Arrays.asList(ans);
    }
    private String abbr(String w, int p) {
        if (w.length() - p <= 2) return w;
        return w.substring(0, p) + (w.length() - p - 1) + w.substring(w.length() - 1);
    }
}
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30

class Solution {
    fun wordsAbbreviation(words: List<String>): List<String> {
        val n = words.size
        val pre = IntArray(n) { 1 }
        val ans = Array(n) { "" }
        fun abbr(w: String, p: Int): String {
            if (w.length - p <= 2) return w
            return w.substring(0, p) + (w.length - p - 1).toString() + w.last()
        }
        while (true) {
            val groups = mutableMapOf<String, MutableList<Int>>()
            for (i in 0 until n) {
                ans[i] = abbr(words[i], pre[i])
                groups.getOrPut(ans[i]) { mutableListOf() }.add(i)
            }
            var unique = true
            for (v in groups.values) {
                if (v.size > 1) {
                    unique = false
                    for (idx in v) pre[idx]++
                }
            }
            if (unique) break
        }
        for (i in 0 until n) {
            if (ans[i].length >= words[i].length) ans[i] = words[i]
        }
        return ans.toList()
    }
}
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27

from typing import List
class Solution:
    def wordsAbbreviation(self, words: List[str]) -> List[str]:
        n = len(words)
        pre = [1] * n
        ans = [''] * n
        def abbr(w: str, p: int) -> str:
            if len(w) - p <= 2:
                return w
            return w[:p] + str(len(w) - p - 1) + w[-1]
        while True:
            groups = {}
            for i in range(n):
                ans[i] = abbr(words[i], pre[i])
                groups.setdefault(ans[i], []).append(i)
            unique = True
            for v in groups.values():
                if len(v) > 1:
                    unique = False
                    for idx in v:
                        pre[idx] += 1
            if unique:
                break
        for i in range(n):
            if len(ans[i]) >= len(words[i]):
                ans[i] = words[i]
        return ans
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40

use std::collections::HashMap;
impl Solution {
    pub fn words_abbreviation(words: Vec<String>) -> Vec<String> {
        let n = words.len();
        let mut pre = vec![1; n];
        let mut ans = vec![String::new(); n];
        fn abbr(w: &str, p: usize) -> String {
            if w.len() <= p + 1 {
                return w.to_string();
            }
            if w.len() - p <= 2 {
                return w.to_string();
            }
            format!("{}{}{}", &w[..p], w.len() - p - 1, &w[w.len()-1..])
        }
        loop {
            let mut groups: HashMap<String, Vec<usize>> = HashMap::new();
            for i in 0..n {
                ans[i] = abbr(&words[i], pre[i]);
                groups.entry(ans[i].clone()).or_default().push(i);
            }
            let mut unique = true;
            for v in groups.values() {
                if v.len() > 1 {
                    unique = false;
                    for &idx in v {
                        pre[idx] += 1;
                    }
                }
            }
            if unique { break; }
        }
        for i in 0..n {
            if ans[i].len() >= words[i].len() {
                ans[i] = words[i].clone();
            }
        }
        ans
    }
}
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31

class Solution {
    wordsAbbreviation(words: string[]): string[] {
        const n = words.length;
        const pre = Array(n).fill(1);
        const ans = Array(n).fill('');
        function abbr(w: string, p: number): string {
            if (w.length - p <= 2) return w;
            return w.slice(0, p) + (w.length - p - 1) + w[w.length - 1];
        }
        while (true) {
            const groups: Record<string, number[]> = {};
            for (let i = 0; i < n; i++) {
                ans[i] = abbr(words[i], pre[i]);
                if (!(ans[i] in groups)) groups[ans[i]] = [];
                groups[ans[i]].push(i);
            }
            let unique = true;
            for (const v of Object.values(groups)) {
                if (v.length > 1) {
                    unique = false;
                    for (const idx of v) pre[idx]++;
                }
            }
            if (unique) break;
        }
        for (let i = 0; i < n; i++) {
            if (ans[i].length >= words[i].length) ans[i] = words[i];
        }
        return ans;
    }
}

Complexity

  • ⏰ Time complexity: O(n * L^2) — For n words of length L, in the worst case, we may need to increase the prefix for each word up to L, and each time we group all n words.
  • 🧺 Space complexity: O(n * L) — For storing abbreviations and prefix lengths.