# Finding the maximum substring for which a given predicate is true

Given a string $S$ of length $N$ and a string predicate $F$, find the maximum substring, $s$, such that $F(s) = \text{true}$. Assume that $F$ satisfies the following:

• If $F(g) = \text{true}$, then any proper sub-string of $g$, above a certain cutoff length $L$, also evaluates true.
• Strings below the cutoff length evaluate to false

What is the best strategy to find $s$ which minimizes the function evaluations?

Naive approaches:

• Sequential search of the string $\mathcal{O}(N^2)$ function evaluations.

I suspect there must be a better way but anything I look up just sends me to Kadane's algorithm. I would appreciate it if anyone has any references which might be useful or know the answer.

• Are we also told $L$? – j_random_hacker Jul 28 '18 at 12:25
• @j_random_hacker yes, $L$ is given in this case. – jman Jul 28 '18 at 18:21

Let's denote $[\exists s: F(s) \wedge |s| = x]$ as $B(x)$. First property of $F$ implies that for any $x > L$

$$B(x) \implies B(x-1)$$

Which by induction implies:

$$B(x) \implies \forall i \in [L, x] : B(i)$$

In other words, if you know that $B(x)$ is true, you don't have to examine lower values of $x$. And if $B(y)$ is false, you know that higher values of $y$ can't give you true, as it would contradict that $B(y)$ is false.

Now you can find maximal $x$ (such that $B(x)$ holds) using binary search. For each iteration of the search, $B(i)$ can be verified in $\mathcal{O}(N)$ calls to $F$: you just need to call it for every substring of fixed length $i$.

In total, this gives you $\mathcal{O}(N \log N)$ calls to $F$.

• Thanks! I definitely should have thought of that in retrospect. – jman Jul 28 '18 at 6:31
• Could you please be more explicit on the binary search you'd perform? And why that implication means that you can do it? – Right leg Jul 28 '18 at 7:45
• @Rightleg is it better now? – Dmitri Urbanowicz Jul 28 '18 at 9:43
• "And if $B(y)$ is false, you know that higher values of $y$ can't give you true, as it would contradict that $B(y)$ is false." -- only when in addition $y > L$, and it's not 100% clear whether $L$ is actually given to us. If it isn't, could it first be found by a similar kind of binary search, before applying the rest of your algorithm? – j_random_hacker Jul 28 '18 at 13:13
• @j_random_hacker Yes, I assumed that $L$ is a given fixed parameter and we never probe lengths below $L$. If $L$ is not known in advance and the maximal string happens to have length $L+1$, then we can only hope for a quantum speedup of Grover's algorithm. – Dmitri Urbanowicz Jul 28 '18 at 14:01