Generate Every Generalized Abbreviation of a Word
Company: Salesforce
Role: Software Engineer
Category: Coding & Algorithms
Difficulty: medium
Interview Round: Onsite
## Problem
Generate every valid generalized abbreviation of a lowercase word. Each character may either remain literal or be included in a positive skip count. Consecutive skipped characters must be represented by one number, never adjacent numeric tokens.
Return all abbreviations in lexicographically ascending string order.
### Function Contract
Implement `generateGeneralizedAbbreviations(word)` and return a string array.
### Constraints & Assumptions
- `0 <= len(word) <= 15`.
- `word` contains only lowercase English letters.
- The empty word has one abbreviation: the empty string.
- Every subset of skipped positions defines exactly one abbreviation, so the result has `2^n` elements.
- Numeric tokens have no leading zero.
### Clarifying Questions to Ask
- Should adjacent skipped positions be merged? Yes, into one count.
- Is `"11"` a valid way to skip two adjacent characters? No; it is parsed as one count of eleven.
- Is output order specified? Yes, lexicographically ascending.
- May duplicate abbreviations occur? No for a lowercase-letter source under this encoding.
```hint Delay writing a skip count
Carry the number of consecutive skipped characters in the recursion. Flush it only when retaining a letter or reaching the end.
```
### Examples
- `word = "word"` produces sixteen abbreviations, including `"word"`, `"1ord"`, `"w1rd"`, `"2rd"`, `"w2d"`, `"3d"`, and `"4"`, returned in lexical order.
- `word = "a"` returns `["1", "a"]`.
- `word = ""` returns `[""]`.
### Evaluation Focus
- Produces every retain-or-skip choice exactly once.
- Merges consecutive skipped characters into one count.
- Handles the empty word and multi-digit counts.
- Uses `O(n)` recursion state apart from the unavoidable `O(n * 2^n)` output, then applies the specified ordering.
### Extensions to Discuss
1. How could results be streamed without storing all of them?
2. What traversal order would produce lexical output without a final sort?
3. How would a maximum number of abbreviated characters prune the recursion?
Overview: Generate every generalized abbreviation of a lowercase word by replacing selected character runs with positive counts. Merge consecutive skipped characters correctly and return the complete result in lexicographic order.
Read the full Salesforce Software Engineer interview experience this question came from