Jobs

Interviews

Discussions

Minimum Unique Word Abbreviation

Hard

Asked by:

13 views

Topics:

StringsBit Manipulation

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"]

Notice that the number represents the number of letters between the left and the right parts if there are any. For example, "ac1d" means the abbreviation of "acid" instead of "a1cid" because the first number represents the number of letters on the left of the group of numbers which is 0, and the right is 1.

Given a target string target and a set of strings in a dictionary dictionary, find an abbreviation of target with the smallest length such that this abbreviation is not in the dictionary.

You can assume:

Each string in the dictionary has the same length as target.
target is not in dictionary.

Example 1:

Input: target = "word", dictionary = ["word"]
Output: "1ord"

Example 2:

Input: target = "apple", dictionary = ["blade"]
Output: "apple"

Constraints:

1 <= target.length <= 12
1 <= dictionary.length <= 1000
1 <= dictionary[i].length <= 12
target and all strings in dictionary are lower-case English letters.

Try coding it in LeetCode

Minimum Unique Word Abbreviation

Hard

Asked by:

13 views

Topics:

StringsBit Manipulation

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 target and a set of strings in a dictionary dictionary, find an abbreviation of target with the smallest length such that this abbreviation is not in the dictionary.

You can assume:

Each string in the dictionary has the same length as target.
target is not in dictionary.

Example 1:

Input: target = "word", dictionary = ["word"]
Output: "1ord"

Example 2:

Input: target = "apple", dictionary = ["blade"]
Output: "apple"

Constraints:

1 <= target.length <= 12
1 <= dictionary.length <= 1000
1 <= dictionary[i].length <= 12
target and all strings in dictionary are lower-case English letters.

Try coding it in LeetCode

Solution

Clarifying Questions

When you get asked this question in a real-life environment, it will often be ambiguous (especially at FAANG). Make sure to ask these questions in that case:

What is the maximum length of each word in the dictionary and the target string?
Can the dictionary contain duplicate words?
If multiple minimum length unique abbreviations exist, is any valid abbreviation acceptable, or is there a specific tie-breaking rule?
Can the dictionary be empty or contain empty strings, and how should those cases be handled?
If no unique abbreviation can be found (e.g., all possible abbreviations clash with words in the dictionary), what should the function return?

Brute Force Solution

Approach

The brute force approach to finding the minimum unique word abbreviation involves trying every possible abbreviation for the target word. We then check each abbreviation to see if it uniquely identifies the target word against the dictionary words. If it does, we compare its length with our current minimum and update if necessary.

Here's how the algorithm would work step-by-step:

First, list out all possible ways to abbreviate the target word. This means considering every combination of keeping letters and replacing sections with numbers.
For each of these abbreviations, go through the dictionary words.
Compare the current abbreviation with each dictionary word. If the abbreviation also matches a dictionary word, it's not unique.
If an abbreviation is unique (doesn't match any other word in the dictionary), calculate its length.
Keep track of the shortest unique abbreviation found so far.
After checking all possible abbreviations, return the shortest unique one.

Code Implementation

def minimum_unique_word_abbreviation_brute_force(target_word, dictionary):

    target_word_length = len(target_word)
    shortest_abbreviation = target_word

    def generate_abbreviations(word, index, current_abbreviation):
        if index == len(word):
            return [current_abbreviation]

        abbreviations = []
        # Keep the current character
        abbreviations.extend(generate_abbreviations(
            word, index + 1, current_abbreviation + word[index]))

        # Abbreviate the current character
        for length in range(1, len(word) - index + 1):
            abbreviations.extend(generate_abbreviations(
                word, index + length, current_abbreviation + str(length)))

        return abbreviations

    all_abbreviations = generate_abbreviations(target_word, 0, "")

    for abbreviation in all_abbreviations:
        is_unique = True

        # Checking against each word in dictionary
        for dictionary_word in dictionary:
            if len(abbreviation) == 0:
                is_unique = False
                break

            if len(dictionary_word) != target_word_length:
                continue

            if matches(abbreviation, dictionary_word):
                is_unique = False
                break

        if is_unique:
            # Comparing the length and updating if needed
            if len(abbreviation) < len(shortest_abbreviation):
                shortest_abbreviation = abbreviation
            elif len(abbreviation) == len(shortest_abbreviation) and \
                    len(abbreviation) < len(target_word) and \
                    len(shortest_abbreviation) == len(target_word):
                shortest_abbreviation = abbreviation

    return shortest_abbreviation

def matches(abbreviation, word):
    abbreviation_index = 0
    word_index = 0

    while abbreviation_index < len(abbreviation) and word_index < len(word):
        if abbreviation[abbreviation_index].isdigit():
            length = 0
            while abbreviation_index < len(abbreviation) and \
                    abbreviation[abbreviation_index].isdigit():
                length = length * 10 + int(abbreviation[abbreviation_index])
                abbreviation_index += 1
            word_index += length
        elif abbreviation[abbreviation_index] == word[word_index]:
            abbreviation_index += 1
            word_index += 1
        else:
            return False

    return abbreviation_index == len(abbreviation) and \
           word_index == len(word)

Big(O) Analysis

Time Complexity

O(2^n * m * n) – Generating all possible abbreviations for the target word, where n is the length of the target word, takes O(2^n) time because each character can either be abbreviated or not, leading to 2 options for each character. For each abbreviation, we iterate through m words in the dictionary. Comparing each abbreviation with a dictionary word takes O(n) time in the worst case, where n is again the length of the target word. Therefore, the overall time complexity is O(2^n * m * n).

Space Complexity

O(2^N * L) – The brute force approach generates all possible abbreviations of the target word, which can be 2^N in the worst case, where N is the length of the target word. Each abbreviation can have a length of up to L, where L is the length of the target word. A temporary data structure is required to store each generated abbreviation for comparison with dictionary words. Thus, the space complexity is proportional to the number of abbreviations times the length of each abbreviation resulting in O(2^N * L).

Optimal Solution

Approach

The goal is to find the shortest abbreviation for a given word that is different from all other words in a dictionary. The key is to use a bitmask to represent which characters in a word are abbreviated and then efficiently check if the resulting abbreviation is unique.

Here's how the algorithm would work step-by-step:

First, filter out words from the dictionary that have a different length than the target word because they cannot possibly cause conflicts.
Represent each possible abbreviation of the target word as a bitmask. Each bit in the bitmask indicates whether the corresponding character in the word is abbreviated or kept as is.
For each bitmask (representing a possible abbreviation), create the abbreviation of the target word.
Also, create the corresponding abbreviation for each of the other words in the dictionary (the ones with the same length).
Check if the abbreviation of the target word is unique, meaning it's different from all the abbreviations of the other words. If so, we found a valid abbreviation.
Keep track of the shortest valid abbreviation found so far. Start checking from the most abbreviated (smallest bitmask count) version. If a smaller bitmask is unique, we know it's shorter and therefore, the best.
Return the shortest unique abbreviation. If no unique abbreviation is found, return the fully unabbreviated word.

Code Implementation

def minimum_unique_word_abbreviation(target_word, dictionary):
    word_length = len(target_word)
    filtered_dictionary = [word for word in dictionary if len(word) == word_length]

    for mask_length in range(word_length + 1):
        for bitmask in combinations(range(word_length), mask_length):
            abbreviation = create_abbreviation(target_word, bitmask)
            is_unique = True

            # Iterate to verify it's unique
            for other_word in filtered_dictionary:
                other_abbreviation = create_abbreviation(other_word, bitmask)
                if abbreviation == other_abbreviation:
                    is_unique = False
                    break

            if is_unique:
                return abbreviation

    return target_word

def create_abbreviation(word, bitmask):
    abbreviation = ""
    last_abbreviated = -1
    count = 0

    for i in range(len(word)):
        if i in bitmask:
            if last_abbreviated == i - 1:
                count += 1
            else:
                if count > 0:
                    abbreviation += str(count)
                count = 1
            last_abbreviated = i
        else:
            if count > 0:
                abbreviation += str(count)
                count = 0
            abbreviation += word[i]

    if count > 0:
        abbreviation += str(count)

    return abbreviation

def combinations(iterable, repeat):
    pool = tuple(iterable)
    number_of_elements = len(pool)
    if repeat > number_of_elements:
        return
    indices = list(range(repeat))
    yield tuple(pool[i] for i in indices)
    while True:
        for i in reversed(range(repeat)):
            if indices[i] != i + number_of_elements - repeat:
                break
        else:
            return
        indices[i] += 1
        for j in range(i+1, repeat):
            indices[j] = indices[j-1] + 1
        yield tuple(pool[i] for i in indices)

#The main idea here is to produce all possible bitmasks to represent abbreviations.
#Then check if the candidate is unique with these abbreviations.
#Finally return the shortest unique version

Big(O) Analysis

Time Complexity

O(2^n * m) – Let n be the length of the target word and m be the number of words in the dictionary that have the same length as the target word. The algorithm iterates through all possible bitmasks of length n, which is 2^n. For each bitmask, it generates the abbreviation of the target word. Then, it iterates through the m words from the dictionary with same length. For each of these m words, it also generates its abbreviation based on the current bitmask. Finally, for each abbreviation of the target word generated, it compares it with the m other generated abbreviations. Therefore, the overall time complexity is O(2^n * m).

Space Complexity

O(M) – The space complexity is dominated by storing the abbreviations of the target word and the other words in the dictionary. The plain English explanation specifies creating abbreviations for each word with the same length as the target word, and each abbreviation has a length proportional to the length of the target word. In the worst case, we store M such abbreviations at a time where M is the length of the target word and all words in the dictionary have the same length, leading to O(M) space. The bitmask itself requires O(M) bits which translates to O(M) space as well because the number of bits will depend on M. No other significant auxiliary space is used.

Edge Cases

Case	How to Handle
Empty target string	Return '1' as the abbreviation according to problem constraints.
Empty dictionary	The shortest possible abbreviation is always the best if the dictionary is empty, so return the length of the target or '1'.
Target string already exists in the dictionary	Return the target string's length as abbreviation since no shortening is needed.
All words in the dictionary are identical to the target	Return the target string's length as the minimum unique abbreviation, as no abbreviation will differentiate it from all words.
Dictionary contains words with different lengths than the target	These words are inherently different and do not impact abbreviation logic, so they can be ignored.
Target string and dictionary words are very long	Bit manipulation using integers might overflow, requiring the use of long data types or alternative representation.
No abbreviation is unique (all abbreviations collide with dictionary words)	The algorithm must ensure it explores all possible abbreviations and return the shortest length if uniqueness is impossible.
Dictionary contains a word that is a prefix of the target	The solution must avoid producing an abbreviation that matches that prefix but isn't a valid abbreviation for the full target.

Empty target string

How to Handle:

Return '1' as the abbreviation according to problem constraints.

Empty dictionary

How to Handle:

The shortest possible abbreviation is always the best if the dictionary is empty, so return the length of the target or '1'.

Target string already exists in the dictionary

How to Handle:

Return the target string's length as abbreviation since no shortening is needed.

All words in the dictionary are identical to the target

How to Handle:

Return the target string's length as the minimum unique abbreviation, as no abbreviation will differentiate it from all words.

Dictionary contains words with different lengths than the target

How to Handle:

These words are inherently different and do not impact abbreviation logic, so they can be ignored.

Target string and dictionary words are very long

How to Handle:

Bit manipulation using integers might overflow, requiring the use of long data types or alternative representation.

No abbreviation is unique (all abbreviations collide with dictionary words)

How to Handle:

The algorithm must ensure it explores all possible abbreviations and return the shortest length if uniqueness is impossible.

Dictionary contains a word that is a prefix of the target

How to Handle:

The solution must avoid producing an abbreviation that matches that prefix but isn't a valid abbreviation for the full target.

Solution

Clarifying Questions

When you get asked this question in a real-life environment, it will often be ambiguous (especially at FAANG). Make sure to ask these questions in that case:

What is the maximum length of each word in the dictionary and the target string?
Can the dictionary contain duplicate words?
If multiple minimum length unique abbreviations exist, is any valid abbreviation acceptable, or is there a specific tie-breaking rule?
Can the dictionary be empty or contain empty strings, and how should those cases be handled?
If no unique abbreviation can be found (e.g., all possible abbreviations clash with words in the dictionary), what should the function return?

Brute Force Solution

Approach

Here's how the algorithm would work step-by-step:

First, list out all possible ways to abbreviate the target word. This means considering every combination of keeping letters and replacing sections with numbers.
For each of these abbreviations, go through the dictionary words.
Compare the current abbreviation with each dictionary word. If the abbreviation also matches a dictionary word, it's not unique.
If an abbreviation is unique (doesn't match any other word in the dictionary), calculate its length.
Keep track of the shortest unique abbreviation found so far.
After checking all possible abbreviations, return the shortest unique one.

Code Implementation

def minimum_unique_word_abbreviation_brute_force(target_word, dictionary):

    target_word_length = len(target_word)
    shortest_abbreviation = target_word

    def generate_abbreviations(word, index, current_abbreviation):
        if index == len(word):
            return [current_abbreviation]

        abbreviations = []
        # Keep the current character
        abbreviations.extend(generate_abbreviations(
            word, index + 1, current_abbreviation + word[index]))

        # Abbreviate the current character
        for length in range(1, len(word) - index + 1):
            abbreviations.extend(generate_abbreviations(
                word, index + length, current_abbreviation + str(length)))

        return abbreviations

    all_abbreviations = generate_abbreviations(target_word, 0, "")

    for abbreviation in all_abbreviations:
        is_unique = True

        # Checking against each word in dictionary
        for dictionary_word in dictionary:
            if len(abbreviation) == 0:
                is_unique = False
                break

            if len(dictionary_word) != target_word_length:
                continue

            if matches(abbreviation, dictionary_word):
                is_unique = False
                break

        if is_unique:
            # Comparing the length and updating if needed
            if len(abbreviation) < len(shortest_abbreviation):
                shortest_abbreviation = abbreviation
            elif len(abbreviation) == len(shortest_abbreviation) and \
                    len(abbreviation) < len(target_word) and \
                    len(shortest_abbreviation) == len(target_word):
                shortest_abbreviation = abbreviation

    return shortest_abbreviation

def matches(abbreviation, word):
    abbreviation_index = 0
    word_index = 0

    while abbreviation_index < len(abbreviation) and word_index < len(word):
        if abbreviation[abbreviation_index].isdigit():
            length = 0
            while abbreviation_index < len(abbreviation) and \
                    abbreviation[abbreviation_index].isdigit():
                length = length * 10 + int(abbreviation[abbreviation_index])
                abbreviation_index += 1
            word_index += length
        elif abbreviation[abbreviation_index] == word[word_index]:
            abbreviation_index += 1
            word_index += 1
        else:
            return False

    return abbreviation_index == len(abbreviation) and \
           word_index == len(word)

Big(O) Analysis

Time Complexity

Space Complexity

Optimal Solution

Approach

Here's how the algorithm would work step-by-step:

First, filter out words from the dictionary that have a different length than the target word because they cannot possibly cause conflicts.
Represent each possible abbreviation of the target word as a bitmask. Each bit in the bitmask indicates whether the corresponding character in the word is abbreviated or kept as is.
For each bitmask (representing a possible abbreviation), create the abbreviation of the target word.
Also, create the corresponding abbreviation for each of the other words in the dictionary (the ones with the same length).
Check if the abbreviation of the target word is unique, meaning it's different from all the abbreviations of the other words. If so, we found a valid abbreviation.
Keep track of the shortest valid abbreviation found so far. Start checking from the most abbreviated (smallest bitmask count) version. If a smaller bitmask is unique, we know it's shorter and therefore, the best.
Return the shortest unique abbreviation. If no unique abbreviation is found, return the fully unabbreviated word.

Code Implementation

def minimum_unique_word_abbreviation(target_word, dictionary):
    word_length = len(target_word)
    filtered_dictionary = [word for word in dictionary if len(word) == word_length]

    for mask_length in range(word_length + 1):
        for bitmask in combinations(range(word_length), mask_length):
            abbreviation = create_abbreviation(target_word, bitmask)
            is_unique = True

            # Iterate to verify it's unique
            for other_word in filtered_dictionary:
                other_abbreviation = create_abbreviation(other_word, bitmask)
                if abbreviation == other_abbreviation:
                    is_unique = False
                    break

            if is_unique:
                return abbreviation

    return target_word

def create_abbreviation(word, bitmask):
    abbreviation = ""
    last_abbreviated = -1
    count = 0

    for i in range(len(word)):
        if i in bitmask:
            if last_abbreviated == i - 1:
                count += 1
            else:
                if count > 0:
                    abbreviation += str(count)
                count = 1
            last_abbreviated = i
        else:
            if count > 0:
                abbreviation += str(count)
                count = 0
            abbreviation += word[i]

    if count > 0:
        abbreviation += str(count)

    return abbreviation

def combinations(iterable, repeat):
    pool = tuple(iterable)
    number_of_elements = len(pool)
    if repeat > number_of_elements:
        return
    indices = list(range(repeat))
    yield tuple(pool[i] for i in indices)
    while True:
        for i in reversed(range(repeat)):
            if indices[i] != i + number_of_elements - repeat:
                break
        else:
            return
        indices[i] += 1
        for j in range(i+1, repeat):
            indices[j] = indices[j-1] + 1
        yield tuple(pool[i] for i in indices)

#The main idea here is to produce all possible bitmasks to represent abbreviations.
#Then check if the candidate is unique with these abbreviations.
#Finally return the shortest unique version

Big(O) Analysis

Time Complexity

Space Complexity

Edge Cases

Case	How to Handle
Empty target string	Return '1' as the abbreviation according to problem constraints.
Empty dictionary	The shortest possible abbreviation is always the best if the dictionary is empty, so return the length of the target or '1'.
Target string already exists in the dictionary	Return the target string's length as abbreviation since no shortening is needed.
All words in the dictionary are identical to the target	Return the target string's length as the minimum unique abbreviation, as no abbreviation will differentiate it from all words.
Dictionary contains words with different lengths than the target	These words are inherently different and do not impact abbreviation logic, so they can be ignored.
Target string and dictionary words are very long	Bit manipulation using integers might overflow, requiring the use of long data types or alternative representation.
No abbreviation is unique (all abbreviations collide with dictionary words)	The algorithm must ensure it explores all possible abbreviations and return the shortest length if uniqueness is impossible.
Dictionary contains a word that is a prefix of the target	The solution must avoid producing an abbreviation that matches that prefix but isn't a valid abbreviation for the full target.

Empty target string

How to Handle:

Return '1' as the abbreviation according to problem constraints.

Empty dictionary

How to Handle:

The shortest possible abbreviation is always the best if the dictionary is empty, so return the length of the target or '1'.

Target string already exists in the dictionary

How to Handle:

Return the target string's length as abbreviation since no shortening is needed.

All words in the dictionary are identical to the target

How to Handle:

Return the target string's length as the minimum unique abbreviation, as no abbreviation will differentiate it from all words.

Dictionary contains words with different lengths than the target

How to Handle:

These words are inherently different and do not impact abbreviation logic, so they can be ignored.

Target string and dictionary words are very long

How to Handle:

Bit manipulation using integers might overflow, requiring the use of long data types or alternative representation.

No abbreviation is unique (all abbreviations collide with dictionary words)

How to Handle:

The algorithm must ensure it explores all possible abbreviations and return the shortest length if uniqueness is impossible.

Dictionary contains a word that is a prefix of the target

How to Handle:

The solution must avoid producing an abbreviation that matches that prefix but isn't a valid abbreviation for the full target.