NUHMAN.com

Introduction

LeetCode 320: Generalized Abbreviation requires us to generate all possible generalized abbreviations of a given word. An abbreviation of a word is formed by replacing some of the letters with the number of times they appear consecutively. For example, the abbreviation "word" can have multiple representations like "w1rd", "wo1d", or "w2", where numbers represent consecutive repeated letters.

The problem is about exploring all possible ways to abbreviate a word, including leaving some letters as-is or replacing sequences of letters with numbers.

Problem Statement

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

Input:

• A string word (1 ≤ word.length ≤ 15).

Output:

• A list of all possible generalized abbreviations, sorted in lexicographical order.

Example

python

# Example 1
Input: word = "word"
Output: ["word", "1ord", "w1rd", "wod", "w1d", "wo1d", "w2", "4"]

# Example 2
Input: word = "a"
Output: ["a", "1"]

Step-by-Step Solution

🧠 Intuition

We need to generate all possible abbreviations by either:

1. Keeping a character as-is.
2. Replacing a sequence of consecutive characters with their count (e.g., "word" → "w1d").

We will use backtracking to explore all possible combinations. The idea is to traverse the word character by character and decide whether to:

• Keep the character as-is.
• Replace the character (or sequence of characters) with a number.

✅ Approach

1. Backtracking:
2. We can recursively build the abbreviation for the word by considering each character and making two choices:

• Either include the character in the abbreviation (as-is).
• Or skip it and increase the count of consecutive characters replaced by a number.

1. Recursive Function:
2. We will define a recursive function that will generate abbreviations by:

• Either appending the character as-is.
• Or appending a number when a sequence of characters is skipped. The base case of the recursion is when we’ve processed all characters in the word.

1. Efficient Backtracking:
2. At each position, we need to track the number of consecutive characters we are replacing with a number. For example, if we are skipping characters in a row, we keep track of how many characters have been skipped and append that number to the abbreviation once we decide to move to the next character.
3. Edge Cases:
4. Handle cases where we might have a word of length 1 or multiple repetitions of the same character.

✅ Python Code

python

class Solution:
    def generateAbbreviations(self, word: str) -> list[str]:
        def backtrack(start, current, count):
            # If we've processed all characters, add the current abbreviation
            if start == len(word):
                result.append(current + (str(count) if count > 0 else ''))
                return
            
            # Case 1: Keep the current character and reset the count
            backtrack(start + 1, current + (str(count) if count > 0 else '') + word[start], 0)
            
            # Case 2: Skip the current character and increment the count
            backtrack(start + 1, current, count + 1)
        
        result = []
        backtrack(0, "", 0)
        return result

Explanation of the Code

1. Backtracking Function:
2. The function backtrack(start, current, count) is defined to recursively build the abbreviation. It takes:

• start: The current index in the word we are processing.
• current: The current abbreviation being built.
• count: The count of consecutive characters we are abbreviating.

1. Base Case:
2. When we reach the end of the word (start == len(word)), we add the current abbreviation to the result. If count > 0, we append the count to the abbreviation. Otherwise, we don’t add a number.
3. Recursive Cases:

• Keep the character: We call the backtracking function with the next index, adding the current character (and the count, if applicable).
• Skip the character: We increment the count and call the backtracking function, effectively skipping the current character in the abbreviation.

1. Generating All Abbreviations:
2. The backtracking function generates all possible abbreviations by exploring all paths in the decision tree (either keeping the character or replacing it with a number).
3. Returning the Result:
4. After all recursive calls are completed, we return the result list, which contains all possible abbreviations.

⏱️ Time and Space Complexity

MetricValueTime ComplexityO(2^n)Space ComplexityO(n)

• Time Complexity:
• The number of possible abbreviations is exponential. Each character can either be included or replaced with a number, leading to O(2^n) possible combinations, where n is the length of the word.
• Space Complexity:
• The space complexity is O(n) because the recursion stack will hold up to n characters (in the worst case).

🔍 Edge Cases

1. Single Character Word:
2. For a word with a single character, there are only two possible abbreviations: the word itself and its abbreviation (1).
3. Example:
4. Input: "a"
5. Output: ["a", "1"]
6. Empty Word:
7. Although not explicitly mentioned in the problem, an empty word should return a list with just the empty string as the abbreviation.
8. Example:
9. Input: ""
10. Output: [""]
11. All Characters the Same:
12. If all characters in the word are the same, the abbreviations will mostly consist of numbers representing the count of consecutive same characters.
13. Example:
14. Input: "aaaa"
15. Output: ["aaaa", "1aaa", "a1aa", "a1a1", "a2aa", "a3a", "4"]
16. Long Word:
17. For longer words (up to length 15), the algorithm should be efficient enough to generate all possible abbreviations using backtracking.

✅ Conclusion

LeetCode 320: Generalized Abbreviation is a problem where backtracking allows us to generate all possible abbreviations of a word by exploring different combinations of keeping or abbreviating consecutive characters. The solution is efficient and concise, leveraging recursive calls to generate all possible strings.