Generalized Abbreviation

Problem

A word’s generalized abbreviation can be constructed by taking any number of non-overlapping and non-adjacent substrings and replacing them with their respective lengths.

• For example, "abcde" can be abbreviated into:
  • "a3e" ("bcd" turned into "3")
  • "1bcd1" ("a" and "e" both turned into "1")
  • "5" ("abcde" turned into "5")
  • "abcde" (no substrings replaced)
• However, these abbreviations are invalid:
  • "23" ("ab" turned into "2" and "cde" turned into "3") is invalid as the substrings chosen are adjacent.
  • "22de" ("ab" turned into "2" and "bc" turned into "2") is invalid as the substring chosen overlap.

Given a string word, return a list of all the possible generalized abbreviations of word. Return the answer in any order.

Examples

Example 1:

1
2

Input: word = "word"
Output: ["4","3d","2r1","2rd","1o2","1o1d","1or1","1ord","w3","w2d","w1r1","w1rd","wo2","wo1d","wor1","word"]

Example 2:

1
2

Input: word = "a"
Output: ["1","a"]

Solution

Method 1 - Backtracking

To generate generalized abbreviations of a given string, we can use a backtracking approach. This approach will help us explore all possible ways to abbreviate the string while adhering to the rules of non-overlapping and non-adjacent substrings.

Our primary goals are:

1. For each character in the string, decide whether to abbreviate it or keep it as is.
2. If abbreviating, ensure that the next abbreviation we consider is not adjacent to the current one.
3. Use a backtracking algorithm to explore all these possibilities.

Here are the steps:

1. Use a recursive function that takes the current position in the string, the current abbreviation being formed, and a count of consecutive abbreviated characters.
2. For each character, there are two choices: abbreviate it or keep it.
   • If abbreviating, increment the count and call the recursive function for the next character.
   • If keeping it, append the abbreviation (if any) and the current character to the result, reset the count, and call the recursive function for the next character.
3. Add the final form of the abbreviation to the result list when the end of the string is reached.

Code

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19

public class Solution {
    public List<String> generateAbbreviations(String word) {
        List<String> ans = new ArrayList<>();
        backtrack(word, 0, "", 0, ans);
        return ans;
    }

    private void backtrack(String word, int pos, String curr, int count, List<String> ans) {
        if (pos == word.length()) {
            if (count > 0) curr += count;
            ans.add(curr);
        } else {
            // Abbreviate this character
            backtrack(word, pos + 1, curr, count + 1, ans);
            // Keep this character
            backtrack(word, pos + 1, curr + (count > 0 ? count : "") + word.charAt(pos), 0, ans);
        }
    }
}

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16

class Solution:
    def generateAbbreviations(self, word: str) -> List[str]:
        ans: List[str] = []
        self.backtrack(word, 0, "", 0, ans)
        return ans
    
    def backtrack(self, word: str, pos: int, curr: str, count: int, ans: List[str]) -> None:
        if pos == len(word):
            if count > 0:
                curr += str(count)
            ans.append(curr)
        else:
            # Abbreviate this character
            self.backtrack(word, pos + 1, curr, count + 1, ans)
            # Keep this character
            self.backtrack(word, pos + 1, curr + (str(count) if count > 0 else '') + word[pos], 0, ans)

Complexity

• ⏰ Time complexity: O(2^n), where n is the length of the string. This is because each character can either be abbreviated or kept, leading to 2^n possible abbreviations.
• 🧺 Space complexity: O(n)  for the recursion stack and intermediate strings.