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.

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

1 Answer 1


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$.

  • $\begingroup$ Thanks! I definitely should have thought of that in retrospect. $\endgroup$
    – jman
    Jul 28, 2018 at 6:31
  • 1
    $\begingroup$ Could you please be more explicit on the binary search you'd perform? And why that implication means that you can do it? $\endgroup$
    – Right leg
    Jul 28, 2018 at 7:45
  • $\begingroup$ @Rightleg is it better now? $\endgroup$ Jul 28, 2018 at 9:43
  • $\begingroup$ "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? $\endgroup$ Jul 28, 2018 at 13:13
  • 1
    $\begingroup$ @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. $\endgroup$ Jul 28, 2018 at 14:01

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.