320. Generalized Abbreviation 🔒
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:
- We need to enumerate all valid possibilities
- At each position, we make a choice (abbreviate or not)
- We need to backtrack when we've explored one path to try other possibilities
- The constraints (non-overlapping, non-adjacent) can be enforced during the recursive exploration
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:
-
Keep the character: We preserve
word[i]
and move on to process the rest of the string starting from positioni+1
. -
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 ati+1
- Or we can abbreviate segments of various lengths
[i, j)
wherej
ranges fromi+1
ton
, and then recursively generate abbreviations for the substring starting atj+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:
-
Keep the current character:
- We keep
word[i]
as-is - Recursively get all abbreviations for
word[i+1:]
by callingdfs(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)]
- We keep
-
Abbreviate a segment starting at position
i
:- Try different segment lengths by iterating
j
fromi+1
ton+1
- This represents abbreviating characters from index
i
toj-1
(exclusive ofj
) - The length of the abbreviated segment is
j - i
- After abbreviating
[i, j)
, we continue from positionj+1
(notj
) to ensure non-adjacent abbreviations - For each segment length:
- Get all abbreviations for the substring starting at
j+1
by callingdfs(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)
- The number
- Add to answer:
ans.append(str(j - i) + (word[j] if j < n else "") + s)
- Get all abbreviations for the substring starting at
- Try different segment lengths by iterating
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 positionj
(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']
- Keep 'a': recurse with
- 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 EvaluatorExample 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:
-
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']
- Keep 'b': Call
- So
dfs(1)
returns: ['bc', 'b1', '1c', '2'] - Prepending 'a' to each: ['abc', 'ab1', 'a1c', 'a2']
- From
-
Abbreviate starting from position 0:
- Abbreviate 'a' only (j=1, length=1): Continue from
dfs(2)
with 'b' as separatordfs(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 separatordfs(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']
- Abbreviate 'a' only (j=1, length=1): Continue from
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 ton-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), requiringO(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.
What are the two properties the problem needs to have for dynamic programming to be applicable? (Select 2)
Recommended Readings
Backtracking Template Prereq DFS with States problems dfs_with_states Combinatorial search problems Combinatorial search problems involve finding groupings and assignments of objects that satisfy certain conditions Finding all permutations combinations subsets and solving Sudoku are classic combinatorial problems The time complexity of combinatorial problems often grows rapidly with the size of
Coding Interview Patterns Your Personal Dijkstra's Algorithm to Landing Your Dream Job The goal of AlgoMonster is to help you get a job in the shortest amount of time possible in a data driven way We compiled datasets of tech interview problems and broke them down by patterns This way
Recursion Recursion is one of the most important concepts in computer science Simply speaking recursion is the process of a function calling itself Using a real life analogy imagine a scenario where you invite your friends to lunch https assets algo monster recursion jpg You first call Ben and ask
Want a Structured Path to Master System Design Too? Don’t Miss This!