Generalized Abbreviation
Medium · Backtracking · about 20 minutes
Asked at Google, Meta, Amazon.
A generalized abbreviation of a word replaces any number of non-overlapping, non-adjacent substrings with their lengths (two replaced substrings can't touch, so "22" would be invalid for "abcd"; use "4"). Return all generalized abbreviations of word, in any order.