Skip to main content
Talentd

Generalized Abbreviation - Solution & Explanation

MediumPremiumFree on FleetCodeStringBacktrackingBit Manipulation12 min readAsked at: Google
Practice this problem

Problem Statement

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.

 

Example 1:

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

Example 2:

Input: word = "a"
Output: ["1","a"]

 

Constraints:

  • 1 <= word.length <= 15
  • word consists of only lowercase English letters.

Approach Overview

Problem Overview: Given a word, generate every possible generalized abbreviation. You can replace any consecutive substring with its length (for example, word β†’ w2d, 1o1d, 4). The task is to enumerate all valid combinations while maintaining the correct abbreviation counts.

Approach 1: DFS Backtracking (Time: O(n * 2^n), Space: O(n))

This approach explores all abbreviation choices using backtracking. At each character you have two decisions: abbreviate it (increase a running count of skipped characters) or keep the character in the output string. When you choose to keep the character, you first append any accumulated count, then append the character itself. The recursion continues until the end of the word, where any remaining count is flushed to the result. This works because each character contributes a binary decision (abbreviate or keep), producing 2^n combinations, while each generated string requires up to O(n) work to build.

The key insight is separating the abbreviation count from the actual string construction. Instead of inserting numbers repeatedly, you carry a running counter and only append it when needed. This keeps the recursion clean and avoids generating invalid formats like consecutive numbers. Backtracking is the most intuitive solution for interviews and clearly demonstrates control over recursion and state management.

Approach 2: Binary Enumeration with Bitmask (Time: O(n * 2^n), Space: O(n))

This method treats the problem as a bit manipulation exercise. For a word of length n, every abbreviation corresponds to a binary mask from 0 to (1 << n) - 1. A bit value of 1 means the character at that index is abbreviated, while 0 means the character is kept. You iterate through each mask and build the abbreviation by counting consecutive 1 bits and writing the count when a 0 appears.

The advantage of this approach is its simplicity: the entire search space is generated through iteration rather than recursion. Each mask represents one decision pattern, and you convert it into a valid abbreviation by scanning the word once. The complexity remains O(n * 2^n) because there are 2^n masks and building each abbreviation requires scanning n characters. This approach is common when practicing enumeration problems involving string transformations.

Recommended for interviews: DFS backtracking is usually the expected explanation because it clearly models the decision process and demonstrates recursion skills. The bitmask enumeration approach is equally efficient and shows strong understanding of combinatorial generation using binary states. Mentioning both signals deeper algorithmic intuition.

Approach 1: DFS

We design a function dfs(i), which returns all possible abbreviations for the string word[i:].

The execution logic of the function dfs(i) is as follows:

If i geq n, it means that the string word has been processed, and we directly return a list composed of an empty string.

Otherwise, we can choose to keep word[i], and then add word[i] to the front of each string in the list returned by dfs(i + 1), and add the obtained result to the answer.

We can also choose to delete word[i] and some characters after it. Suppose we delete word[i..j), then the j th character is not deleted, and then add j - i to the front of each string in the list returned by dfs(j + 1), and add the obtained result to the answer.

Finally, we call dfs(0) in the main function.

The time complexity is O(n times 2^n), and the space complexity is O(n). Where n is the length of the string word.

Code

PythonJavaC++GoTypeScript

Python

Java

C++

Go

TypeScript

Try this approach in the editor β†’

Approach 2: Binary Enumeration

Since the length of the string word does not exceed 15, we can use the method of binary enumeration to enumerate all abbreviations. We use a binary number i of length n to represent an abbreviation, where 0 represents keeping the corresponding character, and 1 represents deleting the corresponding character. We enumerate all i in the range of [0, 2^n), convert it into the corresponding abbreviation, and add it to the answer list.

The time complexity is O(n times 2^n), and the space complexity is O(n). Where n is the length of the string word.

Code

PythonJavaC++Go

Python

Java

C++

Go

Try this approach in the editor β†’

Complexity Comparison

ApproachComplexity
DFSβ€”
Binary Enumerationβ€”

Detailed Complexity Analysis

ApproachTimeSpaceWhen to Use
DFS BacktrackingO(n * 2^n)O(n)Best for interviews and recursive enumeration problems
Binary Enumeration (Bitmask)O(n * 2^n)O(n)Useful when practicing bit manipulation or iterative generation

Video Solution

Leetcode 320. Generalized Abbreviation. δΈ­ζ–‡ β€’ Alina L β€’ 2,099 views views

Watch 9 more video solutions β†’

Frequently Asked Questions

Is Generalized Abbreviation easy or hard?
Generalized Abbreviation is considered a medium difficulty problem. The challenge lies in managing abbreviation counts correctly and generating combinations without producing invalid formats like consecutive numbers.
How to solve Generalized Abbreviation in O(n)?
Generating all abbreviations cannot be done in O(n) because the output itself has size 2^n. The optimal algorithms are DFS backtracking or bitmask enumeration, both running in O(n * 2^n) time due to the exponential number of results.
Generalized Abbreviation Python or Java solution
Python and Java solutions usually implement DFS with parameters for index, current abbreviation count, and the partially built string. Another common implementation iterates over bitmasks from 0 to (1 << n) - 1 and converts each mask into an abbreviation string.
What is the best approach for Generalized Abbreviation?
DFS backtracking is the most common approach. At each character you decide whether to abbreviate it or keep it, while maintaining a counter for consecutive abbreviated characters. This generates all 2^n combinations and builds valid strings in O(n * 2^n) time.
What data structure is used in Generalized Abbreviation?
The typical solution uses recursion with a string builder or dynamic string construction. Backtracking maintains a running count and partial string, while the bitmask approach relies on integer masks and simple string concatenation.
What is the time complexity of Generalized Abbreviation?
The time complexity is O(n * 2^n). A word of length n has 2^n possible abbreviation patterns, and constructing each abbreviation requires up to O(n) work to process characters and counts.
Is Generalized Abbreviation asked at Google, Amazon, or Meta?
Generalized Abbreviation has appeared in interviews at companies that focus on recursion and combinatorial generation problems, including Google and Amazon practice sets. It tests backtracking, bitmask reasoning, and string construction logic.

Ready to solve this problem?

Practice Generalized Abbreviation with our built-in code editor and test cases.

Practice on FleetCode
Previous

Minimum Unique Word Abbreviation

Next

Subsets