We use cookies (including Google cookies) to personalize ads and analyze traffic. By continuing to use our site, you accept our Privacy Policy.

SimplyLeet
TagsDisclaimersPrivacyTermsContactAbout Us

Generalized Abbreviation

Number: 320

Difficulty: Medium

Paid? Yes

Companies: Google

Problem Description

Given a word, generate all its possible generalized abbreviations. A generalized abbreviation is formed by replacing any number of non-overlapping and non-adjacent substrings with their respective lengths. For example, "word" can be abbreviated as "w1rd" (replacing "o" with "1") or "2rd" (replacing "wo" with "2") among other possibilities. Note that abbreviating adjacent or overlapping substrings is not allowed.

Key Insights

  • Use backtracking to explore all possibilities at each character.
  • Maintain a count to represent the number of consecutive abbreviated characters.
  • When a non-abbreviation decision is made, flush the count (if any) into the current string.
  • The recursion depth is driven by the length of the input word.
  • This solution avoids adjacent abbreviations naturally by how the count is managed.

Space and Time Complexity

Time Complexity: O(2^N) where N is the length of the word, due to the binary decision (abbreviate or not) at each character. Space Complexity: O(N) for recursion stack and constructing each abbreviation string.

Solution

We solve this problem using a backtracking approach. At each character, we have two choices:

  1. Abbreviate the current character (i.e., increment a count that keeps track of consecutive abbreviated characters).
  2. Keep the current character and, if there is a pending count, append that count before the character and reset it.

This recursive approach ensures that we generate all valid abbreviations while ensuring that two numbers never appear adjacent (because the count is always flushed before adding a literal character).

We use a helper function that takes the current index, the current built result, and the pending abbreviation count. When the index reaches the end of the word, we append the pending count (if any) to get a complete abbreviation and add it to the result list.

Code Solutions

# Python solution for Generalized Abbreviation

class Solution:
    def generateAbbreviations(self, word: str):
        # Result list to store all abbreviations
        result = []
        
        def backtrack(position, cur, count):
            # When we have processed all characters
            if position == len(word):
                # If there's an abbreviation count left, append it to current path
                if count > 0:
                    cur += str(count)
                result.append(cur)
                return
            
            # Option 1: Abbreviate the current character
            # Increase the count and move to next character without appending the current letter
            backtrack(position + 1, cur, count + 1)
            
            # Option 2: Do not abbreviate the current character
            # First, if there is a pending abbreviation count, append it
            new_cur = cur + (str(count) if count > 0 else "") + word[position]
            # Reset count as we have chosen to keep the character
            backtrack(position + 1, new_cur, 0)
        
        backtrack(0, "", 0)
        return result

# Example usage:
sol = Solution()
print(sol.generateAbbreviations("word"))  # Output will include all valid abbreviations for "word"
← Back to All Questions