``` //9:46AM - 10:27(coding complete) - 10:37PM //1. Define abbreviation algorithm with user defined k //2. How to detect conflicts? How to put back to same order? Use hashmap from abbreviation to new abbreviation and index // key: abbreviation, val: index //3. How to resolve conflicts? Put val length > 1 into a queue. If queue is not empty, increment k and recalculate abbr // for each list in the queue, need to repeat increasing k until every word iin the list is unique // Time complexity: Depends on how many words have conflicting abbre, but worst case O(N * L) where L is max length of word import java.util.*; public class Solution { // words: distinct lowercase words. Return minimal unique abbreviations in order. public List solution(List words) { if (words.size() == 0) { return new ArrayList<>(); } List result = new ArrayList<>(); Map> map = new HashMap<>(); Set visited = new HashSet<>(); Queue conflicts = new LinkedList<>(); for (int i = 0; i < words.size(); i++) { String word = words.get(i); String abbre = calculateAbbreviation(word, 1); result.add(abbre);// can have conflicts List list = map.getOrDefault(abbre, new ArrayList<>()); list.add(i); map.put(abbre, list); if (list.size() > 1 && !visited.contains(abbre)) { conflicts.offer(abbre); visited.add(abbre); } } while(!conflicts.isEmpty()) { String conflictingAbbre = conflicts.poll(); List conflictingWords = map.get(conflictingAbbre); List updatedAbbre = new ArrayList<>(); Set updatedSet = new HashSet<>(); int k = 1; while (updatedSet.size() < conflictingWords.size()) { updatedSet = new HashSet<>(); //reset the set and increment k updatedAbbre = new ArrayList<>();//reset the list k++; for (int i = 0; i < conflictingWords.size(); i++) { int index = conflictingWords.get(i); String shortern = calculateAbbreviation(words.get(index), k); if (updatedSet.contains(shortern)) { break; } updatedSet.add(shortern); updatedAbbre.add(shortern); } } // update the result list for (int i = 0; i < conflictingWords.size(); i++) { result.set(conflictingWords.get(i), updatedAbbre.get(i)); } } return result; } private String calculateAbbreviation(String word, int k) { if (word.length() <= 3) { return word; } int len = word.length(); StringBuilder sb = new StringBuilder(); sb.append(word.substring(0, k)); sb.append(Integer.toString(len-k-1)); sb.append(word.substring(len-1, len)); if (sb.toString().length() == len) { return word; } return sb.toString(); } } ```

Quick Overview

Minimal Unique Word Abbreviations