LeetCode Problem 320

Difficulty: 🟡 Medium
Topics: String, Backtracking, Bit Manipulation

Solution

LeetCode 320, Generalized Abbreviation

Problem Understanding

This problem asks us to generate every possible generalized abbreviation of a given word.

A generalized abbreviation is created by replacing some characters in the string with their count, while preserving the order of the remaining characters. The important restriction is that abbreviated sections must be non-overlapping and non-adjacent. In practice, this means consecutive abbreviated characters must be merged into a single number instead of producing separate adjacent numbers.

For example, consider the word "word":

• "w1r1" means:

• "o" is abbreviated as "1"

• "d" is abbreviated as "1"

• "2rd" means:

• "wo" is abbreviated as "2"

• "4" means:

• the entire word is abbreviated

However, "11rd" is invalid because two adjacent abbreviated sections should instead be merged into "2rd".

The input is a single string word, containing only lowercase English letters. The length of the word is at most 15, which is small enough that exponential solutions are acceptable.

The output should contain every valid generalized abbreviation, in any order.

The constraints are important:

• 1 <= word.length <= 15

• Since each character can either:

• remain as a character

• or become part of an abbreviation

• The total number of possible results is 2^n.

For n = 15, this is:

2^15 = 32768

This is small enough for complete enumeration using backtracking or bit manipulation.

Several edge cases are important:

• A single-character word like "a"
• A word where every character is abbreviated
• A word where no characters are abbreviated
• Consecutive abbreviated characters, which must collapse into one number
• Correct handling of abbreviation counts at the end of the string

A naive implementation often fails when flushing pending abbreviation counts into the output string.

Approaches

Brute Force Approach

The brute-force idea is to consider every subset of characters and decide whether each character is:

• kept as a literal character
• or abbreviated

Since each character has two choices, there are 2^n total combinations.

One way to implement this is using bitmasks:

• 0 means keep the character
• 1 means abbreviate the character

For every mask, we build the corresponding abbreviation string.

For example, for "word":

mask = 1010

means:

• abbreviate 'w'
• keep 'o'
• abbreviate 'r'
• keep 'd'

which becomes:

1o1d

This approach is correct because every valid abbreviation corresponds to exactly one binary decision pattern.

However, the brute-force method repeatedly reconstructs strings from scratch and does not naturally express the recursive structure of the problem. It also becomes harder to reason about correctness and pending abbreviation counts.

Optimal Backtracking Approach

The key observation is that at every position we only have two decisions:

1. Keep the current character
2. Abbreviate the current character

Backtracking is ideal because:

• we explore all combinations recursively
• we maintain the current abbreviation efficiently
• we naturally merge consecutive abbreviated characters using a running count

Instead of immediately appending numbers, we maintain:

• the current index
• the current abbreviation string
• the current count of consecutive abbreviated characters

When we decide to keep a character:

• we first append any pending count
• then append the character itself

When we abbreviate a character:

• we simply increase the running count

This avoids invalid adjacent numbers automatically.

Approach Comparison

Approach	Time Complexity	Space Complexity	Notes
Brute Force	O(2^n × n)	O(n)	Enumerates all bitmasks and builds strings manually
Optimal	O(2^n × n)	O(n)	Backtracking generates abbreviations naturally and cleanly

Although both approaches have the same asymptotic complexity, the backtracking solution is cleaner, easier to reason about, and more efficient in practice.

Algorithm Walkthrough

1. Initialize an empty result list.
2. Define a recursive backtracking function with four parameters:

• index, current position in the word
• current, current abbreviation string being built
• count, number of consecutive abbreviated characters
• result, final output list

3. At each recursive call, check whether we reached the end of the word.

• If yes:

• append any pending abbreviation count

• add the completed abbreviation to the result list

• return

4. For the current character, explore two choices.
5. First choice, abbreviate the character.

• Do not append anything yet.
• Increment count.
• Move to the next index.

6. Second choice, keep the character.

• If count > 0, append the count to the string first.
• Append the actual character.
• Reset count to 0.
• Move to the next index.

7. Continue recursively until all combinations are explored.
8. Return the result list after recursion completes.

Why it works

The algorithm maintains a crucial invariant:

• count always represents the number of consecutive abbreviated characters that have not yet been written into the output string.

Whenever we keep a real character, we flush the count first, ensuring adjacent abbreviated regions are merged correctly into a single number.

Because every character independently chooses between:

• abbreviated
• or preserved

the recursion explores exactly all valid generalized abbreviations.

Python Solution

from typing import List

class Solution:
    def generateAbbreviations(self, word: str) -> List[str]:
        result = []

        def backtrack(index: int, current: str, count: int) -> None:
            if index == len(word):
                if count > 0:
                    current += str(count)

                result.append(current)
                return

            # Option 1: Abbreviate current character
            backtrack(index + 1, current, count + 1)

            # Option 2: Keep current character
            next_current = current

            if count > 0:
                next_current += str(count)

            next_current += word[index]

            backtrack(index + 1, next_current, 0)

        backtrack(0, "", 0)

        return result

The implementation closely follows the recursive decision process.

The backtrack function explores all possibilities starting from a given index.

The count variable is the key idea. Instead of immediately writing abbreviation numbers into the string, the algorithm delays them until necessary. This prevents invalid adjacent numbers such as "11".

When the recursion reaches the end of the word, any remaining pending count is appended before storing the result.

The recursion tree has exactly two branches per character:

• abbreviate it
• keep it

This guarantees complete enumeration of all valid abbreviations.

Go Solution

func generateAbbreviations(word string) []string {
    result := []string{}

    var backtrack func(index int, current string, count int)

    backtrack = func(index int, current string, count int) {
        if index == len(word) {
            if count > 0 {
                current += intToString(count)
            }

            result = append(result, current)
            return
        }

        // Option 1: Abbreviate current character
        backtrack(index+1, current, count+1)

        // Option 2: Keep current character
        nextCurrent := current

        if count > 0 {
            nextCurrent += intToString(count)
        }

        nextCurrent += string(word[index])

        backtrack(index+1, nextCurrent, 0)
    }

    backtrack(0, "", 0)

    return result
}

func intToString(num int) string {
    return fmt.Sprintf("%d", num)
}

The Go implementation follows the same recursive structure as the Python version.

One notable difference is integer-to-string conversion. Go requires explicit formatting using fmt.Sprintf.

Strings in Go are immutable, just like Python, so each recursive branch builds its own string value safely.

The result slice grows dynamically as abbreviations are generated.

Worked Examples

Example 1

Input: "word"

We begin with:

Step	Index	Current	Count
Start	0	""	0

At index 0, character 'w':

Two choices:

Choice 1: Abbreviate 'w'

Index	Current	Count
1	""	1

Next character 'o'.

Again two choices.

If we abbreviate again:

Index	Current	Count
2	""	2

Continuing until the end:

Index	Current	Count
4	""	4

End reached:

"4"

Choice 2: Keep 'd'

Suppose we previously abbreviated three characters.

Index	Current	Count
3	""	3

Keeping 'd' flushes the count:

"3d"

The recursion eventually generates all 16 possibilities.

Example 2

Input: "a"

Initial state:

Step	Index	Current	Count
Start	0	""	0

Two choices:

Abbreviate 'a'

Index	Current	Count
1	""	1

End reached:

"1"

Keep 'a'

Index	Current	Count
1	"a"	0

End reached:

"a"

Final output:

["1", "a"]

Complexity Analysis

Measure	Complexity	Explanation
Time	O(2^n × n)	There are 2^n abbreviations, each may require O(n) string construction
Space	O(n)	Recursive call stack depth is at most n

The algorithm explores a complete binary recursion tree with depth n.

Each leaf produces one abbreviation. Since there are 2^n leaves and constructing each output may take up to O(n) time, the total complexity becomes O(2^n × n).

The auxiliary recursion space is O(n) because the recursion depth never exceeds the length of the word.

The output list itself is not included in auxiliary space analysis.

Test Cases

from typing import List

class Solution:
    def generateAbbreviations(self, word: str) -> List[str]:
        result = []

        def backtrack(index: int, current: str, count: int) -> None:
            if index == len(word):
                if count > 0:
                    current += str(count)

                result.append(current)
                return

            backtrack(index + 1, current, count + 1)

            next_current = current

            if count > 0:
                next_current += str(count)

            next_current += word[index]

            backtrack(index + 1, next_current, 0)

        backtrack(0, "", 0)

        return result

solution = Solution()

# Example 1
result = sorted(solution.generateAbbreviations("word"))
assert len(result) == 16  # 2^4 abbreviations

# Example 2
assert sorted(solution.generateAbbreviations("a")) == ["1", "a"]  # single character

# No abbreviation
assert "abc" in solution.generateAbbreviations("abc")  # original word included

# Full abbreviation
assert "3" in solution.generateAbbreviations("abc")  # all characters abbreviated

# Mixed abbreviations
result = solution.generateAbbreviations("abc")
assert "1b1" in result  # abbreviate first and last characters

# Consecutive abbreviation merging
assert "2c" in result  # not "11c"

# Count correctness
assert "a2" in result  # last two abbreviated

# Output size validation
assert len(solution.generateAbbreviations("abcde")) == 32  # 2^5 results

# Boundary length test
long_result = solution.generateAbbreviations("abcdefghijklmno")
assert len(long_result) == 32768  # 2^15

Test Summary

Test	Why
"word"	Validates standard multi-character generation
"a"	Tests smallest possible input
"abc" contains "abc"	Ensures original word is included
"abc" contains "3"	Ensures full abbreviation works
"1b1"	Tests separated abbreviations
"2c"	Ensures adjacent abbreviations merge correctly
"a2"	Tests suffix abbreviation handling
"abcde" size check	Confirms complete enumeration
15-character word	Validates upper constraint handling

Edge Cases

Single Character Input

A one-character word such as "a" is the smallest valid input.

This case is important because the recursion immediately reaches the base case after one decision. Many implementations accidentally mishandle pending counts when the recursion ends.

The implementation handles this correctly by flushing the count at the base case before appending the result.

Entire Word Abbreviated

For input "abc", the abbreviation "3" must appear.

This tests whether consecutive abbreviated characters are merged into one count rather than producing invalid forms like "111".

The implementation solves this by storing abbreviated length in the count variable and only appending it when necessary.

Ending with an Abbreviation

For input "abc", abbreviations like "a2" are valid.

This case is commonly buggy because the algorithm may forget to append the final count when recursion finishes.

The implementation explicitly checks:

if count > 0:
    current += str(count)

inside the base case, ensuring trailing abbreviations are preserved correctly.

Alternating Characters and Counts

Inputs producing abbreviations like "1b1" verify that the algorithm correctly alternates between literal characters and abbreviation counts.

This ensures:

• counts are flushed at the correct moment
• counts reset properly after adding characters
• recursive branches remain independent

The implementation creates separate string states for each recursive branch, preventing accidental mutation between paths.