Finding the maximum substring for which a given predicate is true

Question

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.