Õptimal Algorithm for Fully Dynamic LZ77

The Lempel-Ziv 77 (LZ77) factorization is a fundamental compression scheme widely used in text processing and data compression. In this work, we study the time complexity of maintaining the LZ77 factorization of a dynamic string. We present an algorithm that dynamically maintains the LZ77 factorization of a string $S$ that undergoes edit operations (character substitutions, insertions, and deletions). The data structure can be built in $\tilde{O}(n)$ time on an initial string $S$ of length $n$, and updates are supported in $\tilde{O}(n^{2/3})$ time, where $n$ is the current length of $S$. We also show that there is no algorithm with polynomially faster update time unless the Strong Exponential Time Hypothesis fails. Our lower bound holds even for the restricted settings in which only substitution operations are allowed, and only the length of the LZ77 factorization is maintained.