Coding Interview PatternsGeneralized Abbreviation
MediumSubsets

Generalized Abbreviation

Explanation & Solution

Practice Problem

Description

Given a word, generate all possible generalized abbreviations of the word.

A generalized abbreviation of a word can be constructed by replacing any number of non-overlapping and non-adjacent substrings with their respective lengths. For example, "abcde" can be abbreviated as "a4", "a1c1e", "5", "2c2", etc.

Two adjacent numbers are not allowed — they must be merged into a single number. For example, "1b1" is valid but "11" is not (it should be "2" instead).

Input: word = "word"

Output:["1o1d","1o2","1or1","1ord","2r1","2rd","3d","4","w1r1","w1rd","w2d","w3","wo1d","wo2","wor1","word"]
0
1o1d
1
1o2
2
1or1
3
1ord
4
2r1
5
2rd
6
3d
7
4
8
w1r1
9
w1rd
10
w2d
11
w3
12
wo1d
13
wo2
14
wor1
15
word

Explanation: Each character is either kept or replaced. Consecutive replaced characters are merged into a single count.

Constraints

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

Approach

Subsets pattern

1. Set Up Backtracking State

  • Track the current index in the word, the current string being built, and a count of consecutively abbreviated characters
  • Start with index = 0, empty string, and count = 0

2. Two Choices at Each Character

  • Abbreviate: Increment the count (do not append anything yet)
  • Keep: Flush the accumulated count (if > 0) into the string, then append the current character and reset count to 0

3. Handle the Base Case

  • When index reaches the end of the word, flush any remaining count and add the built string to the result
  • This ensures trailing abbreviated characters are properly counted

4. Adjacent Number Prevention

  • By tracking a running count instead of appending numbers immediately, adjacent numbers are naturally merged into a single count
  • A number is only flushed to the string when we decide to keep a character or reach the end

5. Sort and Return

  • Sort all generated abbreviations lexicographically for consistent output
  • Return the complete list

Key Insight

  • Each character has exactly two choices (keep or abbreviate), giving 2^n total abbreviations
  • The count accumulator elegantly prevents adjacent numbers
Time
O(n * 2^n)2^n abbreviations, each up to length n
Space
O(n) for recursion depth, plus O(n * 2^n) for storing results

Visualization

Input:
[w, o, r, d]
w0o1r2d3
—

No animation available

Left (L)Right (R)ConvergedDone
0 steps

Solution Code

Previous
Word Search
Next
Letter Case Permutation