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 at 12:25
  • @j_random_hacker yes, $L$ is given in this case. – jman Jul 28 at 18:21
up vote 3 down vote accepted

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 at 6:31
  • 1
    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 at 7:45
  • @Rightleg is it better now? – Dmitri Urbanowicz Jul 28 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 at 13:13
  • 1
    @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 at 14:01

Your Answer

By clicking "Post Your Answer", you acknowledge that you have read our updated terms of service, privacy policy and cookie policy, and that your continued use of the website is subject to these policies.

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