  Shannon's entropy is a definitive lower bound for statistical compression.
Unfortunately, no such clear measure exists for the compressibility of
repetitive strings. Thus, ad hoc measures are employed to estimate the
repetitiveness of strings, e.g., the size $z$ of the Lempel-Ziv parse or the
number $r$ of equal-letter runs of the Burrows-Wheeler transform. A more recent
one is the size $\gamma$ of a smallest string attractor. Let $T$ be a string of
length $n$. A string attractor of $T$ is a set of positions of $T$ capturing
the occurrences of all the substrings of $T$. Unfortunately, Kempa and Prezza
[STOC 2018] showed that computing $\gamma$ is NP-hard. Kociumaka et al. [LATIN
2020] considered a new measure of compressibility that is based on the function
$S_T(k)$ counting the number of distinct substrings of length $k$ of $T$, also
known as the substring complexity of $T$. This new measure is defined as
$\delta= \sup\{S_T(k)/k, k\geq 1\}$ and lower bounds all the relevant ad hoc
measures previously considered. In particular, $\delta\leq \gamma$ always holds
and $\delta$ can be computed in $\mathcal{O}(n)$ time using $\Theta(n)$ working
space. Kociumaka et al. showed that one can construct an $\mathcal{O}(\delta
\log \frac{n}{\delta})$-sized representation of $T$ supporting efficient direct
access and efficient pattern matching queries on $T$. Given that for highly
compressible strings, $\delta$ is significantly smaller than $n$, it is natural
to pose the following question: Can we compute $\delta$ efficiently using
sublinear working space?
  We address this algorithmic challenge by showing the following bounds to
compute $\delta$: $\mathcal{O}(\frac{n^3\log b}{b^2})$ time using
$\mathcal{O}(b)$ space, for any $b\in[1,n]$, in the comparison model; or
$\tilde{\mathcal{O}}(n^2/b)$ time using $\tilde{\mathcal{O}}(b)$ space, for any
$b\in[\sqrt{n},n]$, in the word RAM model.
