Unique Generalized Abbreviations (All Abbreviations of a Word)

• Generalized abbreviation replaces any contiguous run of characters with the count of characters it covers, so loan can become l3, lo2, 4, l1a1, and so on.
• Backtracking makes a binary choice at each character: keep it as a literal, or abbreviate it by incrementing a running skip count.
• Flushing means appending the accumulated count to the result before appending a kept character or when the word ends.
• Uniqueness is guaranteed automatically because each position is decided independently, so no deduplication is needed.
• Complexity is O(n * 2^n) where n is the word length, covering all possible abbreviations.

What is a generalized abbreviation?

A generalized abbreviation of a word is any string where one or more contiguous groups of characters have been replaced by the count of characters in that group. For the word loan, some valid abbreviations are:

• loan (keep all four characters)
• l3 (keep l, abbreviate oan as 3)
• 1o2 (abbreviate l as 1, keep o, abbreviate an as 2)
• 4 (abbreviate the entire word as 4)

The problem asks you to generate all such abbreviations. For a word of length n, there are exactly 2^n abbreviations because each character is independently either kept or counted.

package com.bank.coding;

import java.util.ArrayList;
import java.util.List;

/**
 * Generates all unique generalized abbreviations of a word.
 */
public class GeneralizedAbbreviations {

    public static List<String> generateAbbreviations(String word) {
        List<String> result = new ArrayList<>();
        backtrack(word, 0, new StringBuilder(), 0, result);
        return result;
    }

    private static void backtrack(String word, int index,
                                   StringBuilder current, int count,
                                   List<String> result) {
        int savedLength = current.length();

        if (index == word.length()) {
            if (count > 0) current.append(count);
            result.add(current.toString());
            current.setLength(savedLength); // backtrack
            return;
        }

        // Branch 1: abbreviate this character (increment count)
        backtrack(word, index + 1, current, count + 1, result);

        // Branch 2: keep this character as a literal
        if (count > 0) current.append(count);
        current.append(word.charAt(index));
        backtrack(word, index + 1, current, 0, result);
        current.setLength(savedLength); // backtrack
    }

    public static void main(String[] args) {
        List<String> abbreviations = generateAbbreviations("loan");
        System.out.println("Total: " + abbreviations.size());
        abbreviations.forEach(System.out::println);
    }
}

Total: 16
4
3n
2a1
2an
1o2
1o1n
1oa1
1oan
l3
l2n
l1a1
l1an
lo2
lo1n
loa1
loan

Why does this problem exist?

This problem tests your ability to recognize the subsets pattern hidden inside a word-processing task. Every abbreviation corresponds to a subset of character positions that are kept as literals. The remaining positions are grouped into contiguous runs and replaced by their counts.

In banking, abbreviating product names matters for SMS alerts, receipt printing, and constrained UI displays where character limits are strict.

// Banking scenario: abbreviate product codes for SMS
String productName = "emi";
List<String> options = GeneralizedAbbreviations.generateAbbreviations(productName);
// Produces: 3, 2i, 1m1, 1mi, e2, e1i, em1, emi
// The content team picks the most readable abbreviation

How does the backtracking work internally?

The recursion carries four pieces of state: the current index in the word, a StringBuilder holding the abbreviation built so far, a running count of consecutive characters being abbreviated, and the result list.

At each index, two branches execute:

• Abbreviate branch: increment the count by one and advance the index. Nothing is appended yet because the count keeps accumulating.
• Keep branch: if the count is greater than zero, flush it by appending the number to the builder. Then append the current character as a literal and advance the index with count reset to zero.

At the base case, when the index reaches the word length, flush any remaining count and add the builder's contents to the result list. After each branch, restore the builder to its saved length to undo changes.

// Trace for word = "ab"
// backtrack(0, "", 0)
//   Branch 1: abbreviate 'a' -> backtrack(1, "", 1)
//     Branch 1: abbreviate 'b' -> backtrack(2, "", 2) -> flush "2"
//     Branch 2: keep 'b' -> flush count 1 -> append 'b' -> backtrack(2, "1b", 0) -> "1b"
//   Branch 2: keep 'a' -> append 'a' -> backtrack(1, "a", 0)
//     Branch 1: abbreviate 'b' -> backtrack(2, "a", 1) -> flush "a1"
//     Branch 2: keep 'b' -> append 'b' -> backtrack(2, "ab", 0) -> "ab"
// Result: ["2", "1b", "a1", "ab"]

How does this map to the subsets pattern?

Each abbreviation corresponds to a binary mask of length n, where a 1 means keep the character and a 0 means abbreviate it. For a word of length n, there are 2^n such masks, and each produces a unique abbreviation.

| Mask | Word ab | Abbreviation |
|---|---|---|
| 00 | abbreviate both | 2 |
| 01 | abbreviate a, keep b | 1b |
| 10 | keep a, abbreviate b | a1 |
| 11 | keep both | ab |

Because each mask is unique and each mask produces a different abbreviation, no deduplication step is needed.

// Bit-mask approach (alternative to backtracking)
public static List<String> generateWithBitmask(String word) {
    int n = word.length();
    List<String> result = new ArrayList<>();
    for (int mask = 0; mask < (1 << n); mask++) {
        StringBuilder sb = new StringBuilder();
        int count = 0;
        for (int i = 0; i < n; i++) {
            if ((mask & (1 << i)) != 0) {
                if (count > 0) { sb.append(count); count = 0; }
                sb.append(word.charAt(i));
            } else {
                count++;
            }
        }
        if (count > 0) sb.append(count);
        result.add(sb.toString());
    }
    return result;
}

What are the rules and constraints?

The rules that govern valid abbreviations are:

• A count must be a positive integer. You cannot write 0 in an abbreviation.
• Two counts cannot be adjacent. For example, 1 followed by 2 would look like 12, which is ambiguous. The backtracking naturally avoids this because a count is always followed by a kept character or the end of the word.
• A kept character must appear as its original letter in its original position.
• The full word (all characters kept) and the full count (all characters abbreviated) are both valid abbreviations.

// The constraint that counts cannot be adjacent is handled
// automatically by the backtracking structure.
// When you flush a count, the next thing appended is always
// a literal character, never another count.

What are common mistakes?

The most common mistake is forgetting to flush the running count before appending a kept character. This produces wrong abbreviations where the count and the character are out of order.

// WRONG: does not flush count before keeping a character
private static void backtrackWrong(String word, int index,
                                    StringBuilder current, int count,
                                    List<String> result) {
    if (index == word.length()) {
        if (count > 0) current.append(count);
        result.add(current.toString());
        return;
    }
    // Abbreviate
    backtrackWrong(word, index + 1, current, count + 1, result);
    // Keep -- BUG: appends character without flushing count first
    current.append(word.charAt(index));
    backtrackWrong(word, index + 1, current, count, result);
}
// For "ab" with count=1, this appends 'b' then '1' -> "b1" instead of "1b"

// CORRECT: flush count before appending the kept character
if (count > 0) current.append(count);
current.append(word.charAt(index));
backtrack(word, index + 1, current, 0, result);

Another common mistake is not restoring the StringBuilder length after each branch, which corrupts the builder for sibling branches.

What is the time and space complexity?

The time complexity is O(n * 2^n). There are 2^n abbreviations, and building each abbreviation takes up to O(n) work for the StringBuilder operations. The space complexity is O(n) for the recursion stack depth plus O(n * 2^n) for storing all the results.

// For a word of length 4 (like "loan"):
// 2^4 = 16 abbreviations
// Each abbreviation is at most 4 characters long
// Total output size: at most 64 characters

// For a word of length 10:
// 2^10 = 1024 abbreviations
// This grows exponentially, so the approach is practical only for short words

What about an iterative BFS approach?

Instead of recursive backtracking, you can generate abbreviations level by level using a queue. Start with an empty abbreviation and at each level process one character, branching into keep and abbreviate for each item in the queue.

import java.util.LinkedList;
import java.util.Queue;

public static List<String> generateBFS(String word) {
    int n = word.length();
    Queue<int[]> queue = new LinkedList<>(); // {index, count}
    Queue<StringBuilder> builders = new LinkedList<>();
    queue.add(new int[]{0, 0});
    builders.add(new StringBuilder());
    List<String> result = new ArrayList<>();

    while (!queue.isEmpty()) {
        int[] state = queue.poll();
        StringBuilder sb = builders.poll();
        int idx = state[0], cnt = state[1];

        if (idx == n) {
            if (cnt > 0) sb.append(cnt);
            result.add(sb.toString());
            continue;
        }
        // Abbreviate
        queue.add(new int[]{idx + 1, cnt + 1});
        builders.add(new StringBuilder(sb));
        // Keep
        StringBuilder keepSb = new StringBuilder(sb);
        if (cnt > 0) keepSb.append(cnt);
        keepSb.append(word.charAt(idx));
        queue.add(new int[]{idx + 1, 0});
        builders.add(keepSb);
    }
    return result;
}

The BFS approach uses more memory because it holds all partial abbreviations in the queue simultaneously, but it avoids deep recursion.

What should a senior engineer know?

A senior engineer should recognize that this problem is the subsets pattern applied to string processing. The binary choice at each character maps directly to include-or-exclude in subset enumeration.

The StringBuilder length bookkeeping is the implementation detail that matters most in practice. Saving the length before a branch and restoring it after is the idiomatic Java way to backtrack a mutable builder without creating new strings on every call.

For production use, if the word is longer than about 20 characters, the exponential output becomes impractical. A senior engineer would validate the input length and reject or paginate results for long words.

What are common interview follow-up questions?

Interviewers often ask:

• How would you check if a given string is a valid abbreviation of a given word? Walk both strings simultaneously, advancing the word index by the count when you encounter a digit.
• What is the time complexity of validating one abbreviation? O(n) where n is the word length.
• How would you generate only abbreviations of a fixed length? Add a length constraint to the backtracking pruning.
• How does this relate to the subset sum problem? Both use the same branching structure, but this problem counts character positions instead of summing values.