Lyndon words are strings that are strictly smaller (lexicographically) than all of their proper suffixes. They are the “atoms” of lexicographic ordering — every string has a unique factorization into non-increasing Lyndon words. The Lyndon array of a string records, for each position, the length of the longest Lyndon factor starting there.
Negri et al. (arXiv:2603.17537) define and construct the inverse Lyndon array. Where the Lyndon array records factors that are smaller than all proper suffixes, the inverse Lyndon array records factors that are larger — anti-Lyndon words, strings that are lexicographically greater than every proper suffix starting within them.
The characterization is clean. The inverse Lyndon array can be expressed in terms of the next-greater-suffix array (which records where the next lexicographically larger suffix starts) plus a correction term equal to a longest common extension value. The relationship makes the structure computable in O(n) time — linear in the string length.
The construction is not a trivial mirror of the Lyndon case. Lyndon words have a rich theory connecting them to free Lie algebras, necklace enumeration, and de Bruijn sequences. The inverse objects don't inherit this algebraic richness directly, but they complete a symmetry: if you can decompose strings by their smallest factors, you should also be able to decompose them by their largest. The inverse array fills this gap.
Linear time is the standard for string algorithms — anything more is considered wasteful for a problem on sequences. The O(n) construction confirms that inverse Lyndon structure is computationally as natural as the forward version, despite being conceptually newer. The structure was always in the string; it just hadn't been named.