Generate Every Generalized Abbreviation of a Word

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.

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?