# Minimum Unique Word Abbreviation

This page explains Java solution to problem `Minimum Unique Word Abbreviation` using `Bit Manipulation`.

## Problem Statement

A string such as `"word"` contains the following abbreviations:

["word", "1ord", "w1rd", "wo1d", "wor1", "2rd", "w2d", "wo2", "1o1d", "1or1", "w1r1", "1o2", "2r1", "3d", "w3", "4"]

Given a target string and a set of strings in a dictionary, find an abbreviation of this target string with the smallest possible length such that it does not conflict with abbreviations of the strings in the dictionary.

Each number or letter in the abbreviation is considered `length = 1`. For example, the abbreviation `"a32bc"` has `length = 4`.

Example 1:

Input: target = "apple", dictionary = ["blade"]
Output: "a4"
Explanation: because "5" or "4e" conflicts with "blade"

Example 2:

Input: target = "apple", dictionary = ["plain", "amber", "blade"]
Output: "1p3"
Explanation: (other valid answers include "ap3", "a3e", "2p2", "3le", "3l1")

## Solution

If you have any suggestions in below code, please create a pull request by clicking here.
``````
package com.vc.hard;

import java.util.*;

class MinimumUniqueWordAbbreviation {
public String minAbbreviation(String target, String[] dictionary) {
int targetLength = target.length();

//Calculate binary representation of string in a dictionary
HashSet<Integer> diffs = new HashSet<>();
for(String word: dictionary) {
int diff = 0;
if(word.length() == target.length()) {
for(int i = 0; i < word.length(); i++) {
if(word.charAt(i) != target.charAt(i)) {
//If character is different mark it as 1
diff += (1 << i);
}
}
}
}

if(diffs.size() == 0) return String.valueOf(target.length());

int winner = 0;
int maxConsecutiveZeroCount = Integer.MIN_VALUE;
//Choose the winner from all 2 ^ targetLength possibilities
for(int cand = 0; cand < (1 << targetLength); cand++) {
boolean isValid = true;
for(int diff: diffs) {
if((diff & cand) == 0) {
isValid = false;
break;
}
}

if(isValid) {
int consecutiveZeroCount = 0;
for(int i = 0; i < targetLength - 1; i++) {
if(((cand >> i) & 3) == 0) consecutiveZeroCount++;
}

if(consecutiveZeroCount > maxConsecutiveZeroCount) {
maxConsecutiveZeroCount = consecutiveZeroCount;
winner = cand;
}
}
}

//Convert Winner to String
StringBuilder sb = new StringBuilder();
int count = 0;
for(int i = 0; i < targetLength; i++) {
if((winner & (1 << i)) != 0) { //Need to include character at i in the final result
if(count != 0) {
sb.append(count);
count = 0;
}
sb.append(target.charAt(i));
}
else count++;
}

if(count != 0) sb.append(count);

return sb.toString();
}
}
``````

## Time Complexity

O(2N * M) Where
N is length of an input string target
M is length of an input array dictionary

## Space Complexity

O(M + N) Where
N is length of an input string target
M is length of an input array dictionary