Generalized Abbreviation - Video Solutions

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.