Minimum Unique Word Abbreviation - Practice Coding Problems

Minimum Unique Word Abbreviation - Problem

A string can be abbreviated by replacing any number of non-adjacent substrings with their lengths. For example, a string such as "substitution" could be abbreviated as (but not limited to):

"s10n" ("s ubstitutio n")
"sub4u4" ("sub stit u tion")
"12" ("substitution")
"su3i1u2on" ("su bst i t u ti on")
"substitution" (no substrings replaced)

Note that "s55n" ("s ubsti tutio n") is not a valid abbreviation of "substitution" because the replaced substrings are adjacent.

The length of an abbreviation is the number of letters that were not replaced plus the number of substrings that were replaced. For example, the abbreviation "s10n" has a length of 3 (2 letters + 1 substring) and "su3i1u2on" has a length of 9 (6 letters + 3 substrings).

Given a target string target and an array of strings dictionary, return an abbreviation of target with the shortest possible length such that it is not an abbreviation of any string in dictionary. If there are multiple shortest abbreviations, return any of them.

Input & Output

Example 1 — Basic Case

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

› Output: "a4"

💡 Note: The abbreviation "a4" (representing "apple") is unique because "blade" cannot be abbreviated to "a4" since it doesn't start with 'a'

Example 2 — Need Longer Abbreviation

$ Input: target = "apple", dictionary = ["plain", "amber", "blade"]

› Output: "1p3"

💡 Note: "5" would conflict with "plain", "a4" would conflict with "amber", so "1p3" is the shortest unique abbreviation

Example 3 — No Abbreviation Needed

$ Input: target = "apple", dictionary = ["aple"]

› Output: "apple"

💡 Note: Any abbreviation of "apple" would also match "aple", so we return the full word

Constraints

1 ≤ target.length ≤ 21
0 ≤ dictionary.length ≤ 1000
1 ≤ dictionary[i].length ≤ 100
target and dictionary[i] consist of lowercase English letters
dictionary does not contain target

Visualization

Tap to expand

Understanding the Visualization

Input

Target word and dictionary of conflicting words

Generate

Create all possible abbreviations of target

Filter

Find shortest abbreviation unique from dictionary

Key Takeaway

🎯 Key Insight: Generate all possible abbreviations systematically and filter for shortest unique one

Asked in

G Google 15 f Facebook 8

The key insight is to generate all possible abbreviations and find the shortest one that doesn't conflict with any dictionary word. Best approach uses bit manipulation to represent abbreviation patterns efficiently. Time: O(2^n × m × k), Space: O(1)

Common Approaches

Approach	Time	Space	Notes
✓ Bit Manipulation Optimization	O(2^n × m × k)	O(1)	Use bit masks to efficiently generate all possible abbreviation patterns
Generate All Abbreviations	O(2^n × m × k)	O(2^n)	Generate all possible abbreviations of target and find shortest unique one

Bit Manipulation Optimization — Algorithm Steps

Use bit masks from 0 to 2^n-1 to represent abbreviation patterns
For each mask, generate the corresponding abbreviation
Check uniqueness against dictionary and track shortest valid abbreviation

Visualization

Tap to expand

Step-by-Step Walkthrough

Bit Pattern

Each bit represents abbreviate/keep decision

Generate

Convert bit pattern to abbreviation string

Validate

Check uniqueness and track shortest

Code -

solution.c — C

#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#include <ctype.h>

#define MAX_LEN 100

char* generateAbbrev(char* word, int mask) {
    static char result[MAX_LEN];
    int pos = 0;
    int i = 0;
    int n = strlen(word);
    
    while (i < n) {
        if (mask & (1 << i)) {
            int count = 0;
            while (i < n && (mask & (1 << i))) {
                count++;
                i++;
            }
            pos += sprintf(result + pos, "%d", count);
        } else {
            result[pos++] = word[i];
            i++;
        }
    }
    result[pos] = '\0';
    return result;
}

int isAbbreviation(char* abbr, char* word) {
    int i = 0, j = 0;
    while (i < strlen(abbr) && j < strlen(word)) {
        if (isalpha(abbr[i])) {
            if (abbr[i] != word[j]) return 0;
            i++;
            j++;
        } else {
            if (abbr[i] == '0') return 0;
            int num = 0;
            while (i < strlen(abbr) && isdigit(abbr[i])) {
                num = num * 10 + (abbr[i] - '0');
                i++;
            }
            j += num;
        }
    }
    return i == strlen(abbr) && j == strlen(word);
}

char* solution(char* target, char dictionary[][MAX_LEN], int dict_size) {
    int n = strlen(target);
    int minLen = n;
    static char result[MAX_LEN];
    strcpy(result, target);
    
    for (int mask = 0; mask < (1 << n); mask++) {
        char* abbrev = generateAbbrev(target, mask);
        if (strlen(abbrev) < minLen) {
            int valid = 1;
            for (int i = 0; i < dict_size; i++) {
                if (strcmp(dictionary[i], target) != 0 && isAbbreviation(abbrev, dictionary[i])) {
                    valid = 0;
                    break;
                }
            }
            if (valid) {
                minLen = strlen(abbrev);
                strcpy(result, abbrev);
            }
        }
    }
    
    return result;
}

int main() {
    char target[MAX_LEN];
    char dictionary[10][MAX_LEN];
    int dict_size = 0;
    
    fgets(target, sizeof(target), stdin);
    target[strcspn(target, "\n")] = 0;
    
    char line[500];
    fgets(line, sizeof(line), stdin);
    
    char* token = strtok(line, "[],\"");
    while (token != NULL && dict_size < 10) {
        while (*token == ' ') token++;
        if (strlen(token) > 0) {
            strcpy(dictionary[dict_size++], token);
        }
        token = strtok(NULL, "[],\"");
    }
    
    char* result = solution(target, dictionary, dict_size);
    printf("%s\n", result);
    return 0;
}

Time & Space Complexity

Time Complexity

⏱️

O(2^n × m × k)

2^n bit patterns to check, each validated against m dictionary words of average length k

⚠ Quadratic Growth

Space Complexity

O(1)

Only uses constant extra space for current abbreviation generation

✓ Linear Space

28.5K Views

Medium Frequency

~45 min Avg. Time

892 Likes

Ln 1, Col 1

Smart Actions

💡 Explanation

AI Ready

💡 Suggestion Tab to accept Esc to dismiss

// Output will appear here after running code

Code Editor Closed

Click the red button to reopen

Input & Output

Constraints

Visualization

Related Problems

Common Approaches

Bit Manipulation Optimization — Algorithm Steps

Visualization

Code -

Time & Space Complexity

Select Compiler