Generalized Abbreviation - Practice Coding Problems

Generalized Abbreviation - Problem

A word's generalized abbreviation can be constructed by taking any number of non-overlapping and non-adjacent substrings and replacing them with their respective lengths.

For example, "abcde" can be abbreviated into:

"a3e" ("bcd" turned into "3")
"1bcd1" ("a" and "e" both turned into "1")
"5" ("abcde" turned into "5")
"abcde" (no substrings replaced)

However, these abbreviations are invalid:

"23" ("ab" turned into "2" and "cde" turned into "3") is invalid as the substrings chosen are adjacent.
"22de" ("ab" turned into "2" and "bc" turned into "2") is invalid as the substring chosen overlap.

Given a string word, return a list of all the possible generalized abbreviations of word. Return the answer in any order.

Input & Output

Example 1 — Basic Case

$ Input: word = "word"

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

💡 Note: All possible ways to abbreviate "word" by replacing non-adjacent substrings with their lengths

Example 2 — Short Word

$ Input: word = "a"

› Output: ["1","a"]

💡 Note: Single character can either be abbreviated as "1" or kept as "a"

Example 3 — Two Characters

$ Input: word = "hi"

› Output: ["2","1i","h1","hi"]

💡 Note: Two characters give us 4 combinations: abbreviate both, abbreviate first, abbreviate second, or keep both

Constraints

1 ≤ word.length ≤ 15
word consists of only lowercase English letters

Visualization

Tap to expand

Understanding the Visualization

Input

Original word with each character position

Process

Choose to keep or abbreviate each character (non-adjacent)

Output

All possible valid abbreviations

Key Takeaway

🎯 Key Insight: Each character position has exactly 2 choices: keep the character or include it in an abbreviation group

Asked in

G Google 15 F Facebook 12 a Amazon 8

The key insight is that each character can either be kept as-is or included in an abbreviation group. We can use backtracking to systematically try both choices at each position. Best approach is backtracking with O(2ⁿ × n) time and space complexity.

Common Approaches

Approach	Time	Space	Notes
✓ Optimized Backtracking	O(2ⁿ × n)	O(2ⁿ × n)	Build abbreviations incrementally with early pruning
Brute Force - Try All Combinations	O(2ⁿ × n)	O(2ⁿ × n)	Generate all possible ways to abbreviate or keep each character
Bit Manipulation Approach	O(2ⁿ × n)	O(2ⁿ × n)	Use bit patterns to represent keep/abbreviate decisions

Optimized Backtracking — Algorithm Steps

At each position, try both keeping the character and abbreviating it
Track current abbreviation count to merge consecutive abbreviations
Add complete abbreviation to result when reaching end

Visualization

Tap to expand

Step-by-Step Walkthrough

Decision

At each position: keep character or add to count

Recurse

Continue building with updated state

Backtrack

Try alternative choice and collect results

Code -

solution.c — C

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

char** result;
int resultSize;

void dfs(const char* word, int pos, char* path, int pathLen, int count, int wordLen) {
    if (pos == wordLen) {
        if (count > 0) {
            char countStr[10];
            sprintf(countStr, "%d", count);
            strcat(path, countStr);
            pathLen += strlen(countStr);
        }
        result[resultSize] = malloc(pathLen + 1);
        strcpy(result[resultSize], path);
        resultSize++;
        if (count > 0) {
            path[pathLen - strlen(countStr)] = '\0';
        }
        return;
    }
    
    // Option 1: abbreviate current character
    dfs(word, pos + 1, path, pathLen, count + 1, wordLen);
    
    // Option 2: keep current character
    int prevLen = pathLen;
    if (count > 0) {
        char countStr[10];
        sprintf(countStr, "%d", count);
        strcat(path, countStr);
        pathLen += strlen(countStr);
    }
    char temp[2] = {word[pos], '\0'};
    strcat(path, temp);
    pathLen++;
    dfs(word, pos + 1, path, pathLen, 0, wordLen);
    path[prevLen] = '\0';
}

char** solution(char* word, int* returnSize) {
    int wordLen = strlen(word);
    result = malloc(1000 * sizeof(char*));
    resultSize = 0;
    
    char path[100] = "";
    dfs(word, 0, path, 0, 0, wordLen);
    
    *returnSize = resultSize;
    return result;
}

int main() {
    char word[100];
    fgets(word, sizeof(word), stdin);
    word[strcspn(word, "\n")] = 0;
    
    int returnSize;
    char** result = solution(word, &returnSize);
    
    printf("[");
    for (int i = 0; i < returnSize; i++) {
        printf("\"%s\"", result[i]);
        if (i < returnSize - 1) printf(",");
        free(result[i]);
    }
    printf("]\n");
    free(result);
    return 0;
}

Time & Space Complexity

Time Complexity

⏱️

O(2ⁿ × n)

Each position has 2 choices, and string operations take O(n) time per path

✓ Linear Growth

Space Complexity

O(2ⁿ × n)

Stores all possible abbreviations plus recursion stack depth of O(n)

⚡ Linearithmic Space

33.0K Views

Medium Frequency

~25 min Avg. Time

847 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

Optimized Backtracking — Algorithm Steps

Visualization

Code -

Time & Space Complexity

Select Compiler