Estimate the maximum frequency of substring with given length in a very long character stream

Question

Suppose there is a very long string $S\in \Sigma^N$ with length $N$, where $\Sigma$ is a relatively small alphabet (for example, $\Sigma=\{'a', 'b', \ldots, 'z'\}$). Now, given a budget $B$, the goal is to find the solution of following problem: $$ \begin{align*} \min_{l\in\mathbb{N}} &\quad l \\ \text{s.t. }& \max_{s\subset S, |s|=l} \ \text{freq}(s) < B \end{align*} $$ i.e., I want to find a length $l_c$, such that for "any" substring $s\subset S$ with length $|s|>l$, it occurs no more than $B$ times.

Assume every character in $S$ obeys the same known distribution $D$: $S[i]\sim D, \forall i\in[N]$. Here we can allow some violations in the constraint, only requiring $$ \Pr[\max_{s\subset S, |s|=l} \ \text{freq}(s) < B] > 1-\delta. $$

Currently I'm using a brute force approach, testing each $l$ from small to large, where for each $l$ I scan through the whole string $S$ to determine if there is one substring occur too often. This is very inefficient since $|S|$ is huge.

So I want to know if there exists some sub-linear (w.r.t. $N$) algorithm that can estimate the maximum frequency of substrings with fixed length.

---

Maybe I didn’t make it clear. Here is my problem:

1. Given a constant $B$ and the length of the string $N$, I want to find the minimum length $l$, such that all $l$-long substrings occur no more than $B$ times. Is there a algorithm better than simply testing from small to large?

2. If it's expensive to determine the exact $l$, an approximated $l$ is also acceptable. Here "approximated" has two meanings: $l$ can be smaller than the true $l_c$ as long as there're not too many violating $l$-long substrings; or it can be larger that $l_c$, but not too far away.

3. Furthermore, if the distribution of input character is highly skewed (i.e., some characters occur far more often than others), can I find an approximate or exact $l$, such that all $l$-long substrings starting with some fixed character $s$ occur no more than $B$ times?

Answer 1

If $D$ has high min-entropy, then there's a "sharp cut-off" phenomenom: there's a value $l_0$ depending only on $n,B$ such that the value of $l$ is almost always very close to $l_0$, when $S$ is drawn randomly from $D^n$.

For a simple example, consider the case where $B=2$ and $D$ is the uniform distribution on $\Sigma$. Then

$$l_0 \approx {\lg(n^2/2) \over \lg |\Sigma|},$$

due to the birthday paradox.

Thus, an algorithm can ignore the input string $S$, look only at $B,n$, compute the appropriate $l_0$, and output that. This will be approximately correct, almost all the time.

That's why I say this can be treated as purely a mathematical question, not an algorithmic one.