Generalized abbreviation

String Backtracking Bit Manipulation

60.4% acceptance

Mar 31, 2026

712

232

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.

Solution

Rust

Time O(n²)

Space O(n)

LeetCode

solution.rs

impl Solution {
  pub fn generate_abbreviations(word: String) -> Vec<String> {
    let chars: Vec<char> = word.chars().collect();
    let n = chars.len();
    let mut result = Vec::new();
    // Each bit position decides: 0 = keep char, 1 = abbreviate
    for mask in 0..(1u32 << n) {
      let mut s = String::new();
      let mut count = 0u32;
      for i in 0..n {
        if mask & (1 << i) != 0 {
          count += 1;
        } else {
          if count > 0 {
            s.push_str(&count.to_string());
            count = 0;
          }
          s.push(chars[i]);
        }
      }
      if count > 0 {
        s.push_str(&count.to_string());
      }
      result.push(s);
    }
    result
  }
}