Generalized Abbreviation

Generalized Abbreviation

What is this problem about?

The Generalized Abbreviation interview question asks you to generate all possible generalized abbreviations of a given word. An abbreviation is created by replacing any number of non-overlapping, non-adjacent substrings with their lengths. For example, "word" can be abbreviated as "4", "3d", "w3", "w2d", "w1r1", etc. You need to return a list of all valid abbreviations.

Why is this asked in interviews?

Google uses this Backtracking interview pattern to test a candidate's ability to explore a full state space (generating $2^N$ combinations). It evaluates your recursion skills, particularly how you manage state strings and counts during branching. It's a classic subset-generation problem with formatting constraints.

Algorithmic pattern used

This problem is solved using Backtracking / Recursion. At each character in the string, you have two choices:

1. Keep the character: If there is a running count of abbreviated characters, append that count to the string, reset the count to 0, and then append the current character.
2. Abbreviate the character: Increment the running count of abbreviated characters by 1 and move to the next character. When you reach the end of the string, if there's a non-zero count remaining, append it.

Example explanation

Word: "ab"

1. Start at 'a', count = 0.
2. Keep 'a': string="a", count=0. Move to 'b'.
   • Keep 'b': string="ab", count=0. End. Result: "ab".
   • Abbrev 'b': count=1. End. Append count. Result: "a1".
3. Abbrev 'a': count=1. Move to 'b'.
   • Keep 'b': append count (1), string="1", count=0. Append 'b'. Result: "1b".
   • Abbrev 'b': count=2. End. Append count. Result: "2". Final output: ["ab", "a1", "1b", "2"].

Common mistakes candidates make

• Adjacent Numbers: Generating invalid abbreviations like "11" instead of "2". The backtracking state must accumulate the count before appending it to the string.
• String Concatenation Overhead: In languages like Java or C++, doing string + char inside the recursive call creates many temporary objects. Using a StringBuilder and backtracking (undoing the append) is more memory efficient.
• Missing the final count: Forgetting to append the accumulated count when the recursion reaches the end of the word.

Interview preparation tip

This problem can also be solved using Bit Manipulation. Since there are $2^N$ combinations, you can loop from $0$ to $2^N-1$. For each number, treat the $i^{th}$ bit as a flag: if 1, abbreviate the $i^{th}$ character; if 0, keep it. This avoids recursion entirely and is highly impressive to interviewers.