Facebook Pixel

320. Generalized Abbreviation 🔒

MediumBit ManipulationStringBacktracking
Leetcode Link

Problem Description

You need to generate all possible generalized abbreviations of a given string.

A generalized abbreviation is created by replacing any number of non-overlapping and non-adjacent substrings with their lengths.

Rules for valid abbreviations:

  • You can replace any substring with its length (the number of characters)
  • The replaced substrings must NOT overlap with each other
  • The replaced substrings must NOT be adjacent (there must be at least one character between them that is not abbreviated)

Examples for the word "abcde":

Valid abbreviations include:

  • "a3e" - substring "bcd" is replaced with "3"
  • "1bcd1" - "a" is replaced with "1" and "e" is replaced with "1"
  • "5" - the entire string "abcde" is replaced with "5"
  • "abcde" - no replacements made

Invalid abbreviations:

  • "23" - would require replacing "ab" with "2" and "cde" with "3", but these substrings are adjacent (no character between them)
  • "22de" - would require replacing "ab" with "2" and "bc" with "2", but these substrings overlap (they share the character 'b')

Given a string word, return a list containing all possible generalized abbreviations. The order of the result doesn't matter.

Flowchart Walkthrough

First, let's pin down the algorithm using the Flowchart. Here's a step-by-step walkthrough:

Is it a graph?

  • No: The problem involves string manipulation and generating abbreviations, not nodes and edges as in graph problems.

Need to solve for kth smallest/largest?

  • No: We need to generate all possible abbreviations, not find a specific kth element.

Involves Linked Lists?

  • No: The problem deals with strings and their abbreviations, not linked list data structures.

Does the problem have small constraints?

  • Yes: The problem requires generating all possible abbreviations of a string. Since the number of possible abbreviations grows exponentially (each character can either be kept or be part of an abbreviated segment), this is typically feasible only for strings with small lengths.

Brute force / Backtracking?

  • Yes: We need to explore all possible ways to abbreviate the string. At each position, we have choices: either keep the character as-is, or abbreviate it along with subsequent characters. This requires systematically exploring all combinations while respecting the constraints (non-overlapping, non-adjacent), which is perfectly suited for backtracking.

Conclusion: The flowchart suggests using a backtracking approach for generating all generalized abbreviations. This makes sense because:

  1. We need to enumerate all valid possibilities
  2. At each position, we make a choice (abbreviate or not)
  3. We need to backtrack when we've explored one path to try other possibilities
  4. The constraints (non-overlapping, non-adjacent) can be enforced during the recursive exploration
Quick Interview Experience
Help others by sharing your interview experience
Have you seen this problem before?

Intuition

When we look at this problem, we need to think about how to generate all possible ways to abbreviate a string. At each character position, we face a fundamental decision: should we keep this character as-is, or should we abbreviate it?

Let's think through this systematically. For any position i in the string, we have two main choices:

  1. Keep the character: We preserve word[i] and move on to process the rest of the string starting from position i+1.

  2. Abbreviate a segment: We can choose to abbreviate a segment starting from position i. But how long should this segment be? It could be just one character, two characters, three, and so on, up to the end of the string.

The key insight is that after we abbreviate a segment from position i to position j-1, we need to ensure the next abbreviated segment (if any) is not adjacent. This is automatically handled if we continue processing from position j+1 instead of j, because the character at position j acts as a separator.

This naturally leads to a recursive approach where at each position i:

  • We can keep word[i] and recursively generate all abbreviations for the substring starting at i+1
  • Or we can abbreviate segments of various lengths [i, j) where j ranges from i+1 to n, and then recursively generate abbreviations for the substring starting at j+1

The beauty of this approach is that by always skipping at least one position after an abbreviation (going to j+1 instead of j), we automatically ensure that abbreviated segments are never adjacent. The non-overlapping property is naturally maintained because we process positions sequentially and never go back.

Each recursive call returns all possible abbreviations for the substring it's responsible for, and we combine these results with our current choices to build up the complete set of abbreviations.

Solution Approach

The implementation uses a depth-first search (DFS) approach with a recursive helper function dfs(i) that generates all possible abbreviations for the substring word[i:].

Base Case: When i >= n (where n is the length of the word), we've processed the entire string. Return a list containing an empty string [""] as there's nothing left to abbreviate.

Recursive Cases:

For each position i, we explore two types of choices:

  1. Keep the current character:

    • We keep word[i] as-is
    • Recursively get all abbreviations for word[i+1:] by calling dfs(i + 1)
    • Prepend word[i] to each returned abbreviation
    • Add these results to our answer list: ans = [word[i] + s for s in dfs(i + 1)]
  2. Abbreviate a segment starting at position i:

    • Try different segment lengths by iterating j from i+1 to n+1
    • This represents abbreviating characters from index i to j-1 (exclusive of j)
    • The length of the abbreviated segment is j - i
    • After abbreviating [i, j), we continue from position j+1 (not j) to ensure non-adjacent abbreviations
    • For each segment length:
      • Get all abbreviations for the substring starting at j+1 by calling dfs(j + 1)
      • Build the abbreviation by combining:
        • The number str(j - i) (length of abbreviated segment)
        • The character at position j if it exists (word[j] if j < n else "") - this acts as a separator
        • Each abbreviation returned from dfs(j + 1)
      • Add to answer: ans.append(str(j - i) + (word[j] if j < n else "") + s)

Key Implementation Details:

  • The function processes the string from left to right, making decisions at each position
  • By jumping to j+1 after abbreviating [i, j), we ensure that the character at position j (if it exists) acts as a separator, preventing adjacent abbreviations
  • The recursive structure naturally handles all combinations of keeping and abbreviating different parts of the string
  • Starting the recursion with dfs(0) generates all abbreviations for the entire word

Example Walkthrough for "ab":

  • dfs(0) can:
    • Keep 'a': recurse with dfs(1), which gives ['b', '1'], resulting in ['ab', 'a1']
    • Abbreviate 'a' (segment [0,1)): continue from dfs(2) with 'b' as separator, giving ['1b']
    • Abbreviate 'ab' (segment [0,2)): continue from dfs(3), giving ['2']
  • Final result: ['ab', 'a1', '1b', '2']

Ready to land your dream job?

Unlock your dream job with a 3-minute evaluator for a personalized learning plan!

Start Evaluator

Example Walkthrough

Let's walk through the algorithm with the string "abc" to see how it generates all possible abbreviations.

Starting with dfs(0) - Processing position 0:

At position 0, we have character 'a'. We can either:

  1. Keep 'a': Call dfs(1) to process the rest "bc"

    • From dfs(1) at 'b', we can:
      • Keep 'b': Call dfs(2) → gives us ['c', '1'] → prepend 'b' → ['bc', 'b1']
      • Abbreviate 'b' (length 1): Skip to dfs(3) with 'c' as separator → gives ['1c']
      • Abbreviate 'bc' (length 2): Skip to dfs(4) → gives ['2']
    • So dfs(1) returns: ['bc', 'b1', '1c', '2']
    • Prepending 'a' to each: ['abc', 'ab1', 'a1c', 'a2']
  2. Abbreviate starting from position 0:

    • Abbreviate 'a' only (j=1, length=1): Continue from dfs(2) with 'b' as separator
      • dfs(2) at 'c' gives: ['c', '1']
      • Combine: '1' + 'b' + each result → ['1bc', '1b1']
    • Abbreviate 'ab' (j=2, length=2): Continue from dfs(3) with 'c' as separator
      • dfs(3) is beyond bounds, returns ['']
      • Combine: '2' + 'c' + '' → ['2c']
    • Abbreviate 'abc' (j=3, length=3): Continue from dfs(4)
      • dfs(4) is beyond bounds, returns ['']
      • Combine: '3' + '' + '' → ['3']

Combining all results:

  • From keeping 'a': ['abc', 'ab1', 'a1c', 'a2']
  • From abbreviating 'a': ['1bc', '1b1']
  • From abbreviating 'ab': ['2c']
  • From abbreviating 'abc': ['3']

Final answer: ['abc', 'ab1', 'a1c', 'a2', '1bc', '1b1', '2c', '3']

Notice how the algorithm naturally prevents adjacent abbreviations. When we abbreviate 'a' (position 0), we jump to position 2, ensuring 'b' acts as a separator. This prevents invalid forms like "11c" which would require adjacent abbreviations of 'a' and 'b'.

Solution Implementation

1class Solution:
2    def generateAbbreviations(self, word: str) -> List[str]:
3        """
4        Generate all possible abbreviations of a word.
5        An abbreviation replaces any number of consecutive characters with their count.
6      
7        Args:
8            word: The input string to generate abbreviations for
9          
10        Returns:
11            List of all possible abbreviations
12        """
13      
14        def generate_from_index(start_index: int) -> List[str]:
15            """
16            Recursively generate abbreviations starting from a given index.
17          
18            Args:
19                start_index: The current position in the word
20              
21            Returns:
22                List of abbreviations for the substring from start_index to end
23            """
24            # Base case: if we've processed the entire word
25            if start_index >= word_length:
26                return [""]
27          
28            abbreviations = []
29          
30            # Option 1: Keep the current character as-is (no abbreviation)
31            # Get all abbreviations for the remaining substring
32            remaining_abbreviations = generate_from_index(start_index + 1)
33            for suffix in remaining_abbreviations:
34                abbreviations.append(word[start_index] + suffix)
35          
36            # Option 2: Abbreviate from current position
37            # Try abbreviating different lengths starting from current index
38            for end_index in range(start_index + 1, word_length + 1):
39                # Calculate the length of characters to abbreviate
40                abbreviation_length = end_index - start_index
41              
42                # Get all possible abbreviations for what comes after this abbreviation
43                for suffix in generate_from_index(end_index + 1):
44                    # Build the abbreviation: number + next character (if exists) + suffix
45                    if end_index < word_length:
46                        # There's a character after the abbreviated section
47                        abbreviations.append(str(abbreviation_length) + word[end_index] + suffix)
48                    else:
49                        # We've abbreviated to the end of the word
50                        abbreviations.append(str(abbreviation_length) + suffix)
51          
52            return abbreviations
53      
54        # Store word length for easier access
55        word_length = len(word)
56      
57        # Start generating abbreviations from index 0
58        return generate_from_index(0)
59
1class Solution {
2    private String word;
3    private int wordLength;
4
5    /**
6     * Generates all possible abbreviations of the given word.
7     * An abbreviation replaces any number of consecutive characters with their count.
8     * 
9     * @param word the input string to generate abbreviations for
10     * @return a list of all possible abbreviations
11     */
12    public List<String> generateAbbreviations(String word) {
13        this.word = word;
14        this.wordLength = word.length();
15        return generateFromIndex(0);
16    }
17
18    /**
19     * Recursively generates abbreviations starting from the given index.
20     * 
21     * @param startIndex the current position in the word
22     * @return a list of all possible abbreviations from this index onwards
23     */
24    private List<String> generateFromIndex(int startIndex) {
25        // Base case: reached the end of the word
26        if (startIndex >= wordLength) {
27            return List.of("");
28        }
29      
30        List<String> abbreviations = new ArrayList<>();
31      
32        // Option 1: Keep the current character as-is (no abbreviation)
33        for (String suffix : generateFromIndex(startIndex + 1)) {
34            abbreviations.add(word.charAt(startIndex) + suffix);
35        }
36      
37        // Option 2: Abbreviate from current position with different lengths
38        for (int endIndex = startIndex + 1; endIndex <= wordLength; endIndex++) {
39            // Calculate the number of characters to abbreviate
40            int abbreviationLength = endIndex - startIndex;
41          
42            // Get the character after abbreviation (if exists)
43            String nextChar = (endIndex < wordLength) ? String.valueOf(word.charAt(endIndex)) : "";
44          
45            // Generate all possible suffixes starting after the abbreviation
46            for (String suffix : generateFromIndex(endIndex + 1)) {
47                // Build the abbreviation: number + next character + remaining suffix
48                abbreviations.add(abbreviationLength + nextChar + suffix);
49            }
50        }
51      
52        return abbreviations;
53    }
54}
55
1class Solution {
2public:
3    vector<string> generateAbbreviations(string word) {
4        int wordLength = word.size();
5      
6        // Recursive function to generate abbreviations starting from index 'startIndex'
7        function<vector<string>(int)> generateFromIndex = [&](int startIndex) -> vector<string> {
8            // Base case: reached end of word
9            if (startIndex >= wordLength) {
10                return {""};
11            }
12          
13            vector<string> abbreviations;
14          
15            // Option 1: Keep the current character as-is (don't abbreviate)
16            for (const auto& suffix : generateFromIndex(startIndex + 1)) {
17                string currentChar(1, word[startIndex]);
18                abbreviations.emplace_back(currentChar + suffix);
19            }
20          
21            // Option 2: Abbreviate from current position
22            // Try abbreviating different lengths starting from current index
23            for (int endIndex = startIndex + 1; endIndex <= wordLength; ++endIndex) {
24                // Generate all possible abbreviations after this abbreviated segment
25                for (const auto& suffix : generateFromIndex(endIndex + 1)) {
26                    // If we haven't reached the end, add the character at endIndex
27                    string nextChar = (endIndex < wordLength) ? string(1, word[endIndex]) : "";
28                    // Create abbreviation: number of chars abbreviated + next char + remaining suffix
29                    int abbreviatedCount = endIndex - startIndex;
30                    abbreviations.emplace_back(to_string(abbreviatedCount) + nextChar + suffix);
31                }
32            }
33          
34            return abbreviations;
35        };
36      
37        // Start generating from index 0
38        return generateFromIndex(0);
39    }
40};
41
1/**
2 * Generates all possible abbreviations of a word.
3 * An abbreviation replaces any number of consecutive characters with their count.
4 * For example, "word" can be abbreviated as "4", "w3", "wo2", "wor1", "1o2", etc.
5 * 
6 * @param word - The input string to generate abbreviations for
7 * @returns An array of all possible abbreviations
8 */
9function generateAbbreviations(word: string): string[] {
10    const wordLength: number = word.length;
11  
12    /**
13     * Recursive helper function to generate abbreviations starting from index i
14     * 
15     * @param currentIndex - The current position in the word being processed
16     * @returns An array of abbreviation suffixes starting from currentIndex
17     */
18    const generateFromIndex = (currentIndex: number): string[] => {
19        // Base case: reached the end of the word
20        if (currentIndex >= wordLength) {
21            return [''];
22        }
23      
24        const abbreviations: string[] = [];
25      
26        // Option 1: Keep the current character as-is (no abbreviation)
27        const suffixesWithoutAbbreviation: string[] = generateFromIndex(currentIndex + 1);
28        for (const suffix of suffixesWithoutAbbreviation) {
29            abbreviations.push(word[currentIndex] + suffix);
30        }
31      
32        // Option 2: Abbreviate from current position to various end positions
33        for (let endIndex = currentIndex + 1; endIndex <= wordLength; ++endIndex) {
34            // Calculate the count of characters being abbreviated
35            const abbreviationCount: number = endIndex - currentIndex;
36          
37            // Get the character immediately after the abbreviated section (if exists)
38            const nextCharacter: string = endIndex < wordLength ? word[endIndex] : '';
39          
40            // Generate suffixes starting from position after the abbreviated section
41            const suffixesAfterAbbreviation: string[] = generateFromIndex(endIndex + 1);
42          
43            // Combine the abbreviation count, next character, and suffixes
44            for (const suffix of suffixesAfterAbbreviation) {
45                abbreviations.push(abbreviationCount.toString() + nextCharacter + suffix);
46            }
47        }
48      
49        return abbreviations;
50    };
51  
52    // Start the recursive generation from index 0
53    return generateFromIndex(0);
54}
55

Time and Space Complexity

Time Complexity: O(n × 2^n)

The algorithm generates all possible abbreviations of a word by making decisions at each position: either keep the character or abbreviate a sequence of characters. At each position i, we have two main choices:

  • Keep the current character and continue (leading to 2^n possible combinations)
  • Abbreviate different lengths starting from position i (from 1 to n-i characters)

For each of the 2^n possible abbreviations, we need O(n) time to construct the string. Therefore, the total time complexity is O(n × 2^n).

Space Complexity: O(n)

The space complexity consists of:

  • Recursion stack depth: The maximum depth of recursion is n (when we process each character one by one), requiring O(n) stack space
  • Temporary strings during construction: While we create multiple strings in the result, we only need to consider the space for the recursion stack and temporary variables at any given moment
  • The output list itself contains 2^n strings, but this is typically not counted in space complexity analysis as it's the required output

Therefore, excluding the output storage, the space complexity is O(n).

Common Pitfalls

1. Incorrect Handling of Adjacent Abbreviations

The Pitfall: A common mistake is to continue from position j instead of j+1 after abbreviating the segment [i, j). This would create invalid adjacent abbreviations.

Incorrect Implementation:

# WRONG: This allows adjacent abbreviations
for end_index in range(start_index + 1, word_length + 1):
    abbreviation_length = end_index - start_index
    # Continuing from end_index allows adjacent abbreviations
    for suffix in generate_from_index(end_index):  # ❌ Should be end_index + 1
        abbreviations.append(str(abbreviation_length) + suffix)

Why it's wrong:

  • If we abbreviate [0, 2) in "abcde" to get "2", then continue from index 2, we could immediately abbreviate [2, 4) to get "2" again, resulting in "22e"
  • This creates adjacent numbers without any character separator, violating the non-adjacent rule

Correct Solution:

# CORRECT: Skip to j+1 to ensure non-adjacent abbreviations
for end_index in range(start_index + 1, word_length + 1):
    abbreviation_length = end_index - start_index
    # Skip the character at end_index (if it exists) to act as separator
    for suffix in generate_from_index(end_index + 1):  # ✓ Correctly skip one position
        if end_index < word_length:
            # Include the separator character
            abbreviations.append(str(abbreviation_length) + word[end_index] + suffix)
        else:
            # No separator needed at the end
            abbreviations.append(str(abbreviation_length) + suffix)

2. Forgetting to Handle the Separator Character

The Pitfall: Another mistake is forgetting to include the character at position j when building the abbreviation after abbreviating segment [i, j).

Incorrect Implementation:

# WRONG: Missing the separator character
for end_index in range(start_index + 1, word_length + 1):
    abbreviation_length = end_index - start_index
    for suffix in generate_from_index(end_index + 1):
        # Missing word[end_index] when it exists
        abbreviations.append(str(abbreviation_length) + suffix)  # ❌ 

Why it's wrong:

  • For "abc", if we abbreviate "a" (segment [0,1)), we should get "1bc", not "1c"
  • The character at position 1 ('b') must be included as it serves as the separator

Correct Solution: Always check if there's a character at position end_index and include it:

if end_index < word_length:
    # Include the character at end_index as separator
    abbreviations.append(str(abbreviation_length) + word[end_index] + suffix)
else:
    # We've abbreviated to the end, no separator needed
    abbreviations.append(str(abbreviation_length) + suffix)

3. Inefficient String Concatenation

The Pitfall: While not affecting correctness, repeatedly concatenating strings in Python can be inefficient for longer words due to string immutability.

Less Efficient:

abbreviations.append(word[start_index] + suffix)  # Creates new string each time

More Efficient Alternative: For performance-critical scenarios with very long words, consider using a list to build the result:

def generate_from_index(start_index: int, current_path: List[str]) -> None:
    if start_index >= word_length:
        result.append(''.join(current_path))
        return
  
    # Keep current character
    current_path.append(word[start_index])
    generate_from_index(start_index + 1, current_path)
    current_path.pop()
  
    # Abbreviate segments
    for end_index in range(start_index + 1, word_length + 1):
        current_path.append(str(end_index - start_index))
        if end_index < word_length:
            current_path.append(word[end_index])
            generate_from_index(end_index + 1, current_path)
            current_path.pop()
        else:
            generate_from_index(end_index + 1, current_path)
        current_path.pop()

This approach modifies a single list rather than creating new strings at each step, which can be more efficient for very long input strings.

Discover Your Strengths and Weaknesses: Take Our 3-Minute Quiz to Tailor Your Study Plan:

What are the two properties the problem needs to have for dynamic programming to be applicable? (Select 2)


Recommended Readings

Want a Structured Path to Master System Design Too? Don’t Miss This!

Load More