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.

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

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

Solution

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);
                    }
                }
                diffs.add(diff);
            }
        }

        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(2^N * 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