How to check if $m$ numbers in a sequence satisfy a condition, such that all these numbers are spaced apart by at least $k$? Suppose we have a sequence $s$ with $n$ elements from $s[1..n]$. I want to check if there exists $m \leq n$ elements in this sequence that each satisfy some simple condition (that can be tested in $O(1)$ for each $s[i]$), such that all of these elements are spaced apart by at least $k$. Is there an algorithm that can achieve this in $O(n)$ time?

For example, suppose we have $s=[3, 4, 13, 2, 6, 4, 1, 9, 11, 5]$ and we are trying to verify if there exists $m=3$ elements that satisfy the condition $s[i] \leq 4$ and are spaced apart by at least $k=2$. This is true because $s[1] = 3, s[4] = 2, s[7] = 1$ and $s[1], s[4], s[7]$ are spaced apart by at least $2$.

A naive solution that I thought of involved iterating through the sequence and recording each $s[i]$ that satisfies the condition, and then for each $s[i]$, trying to find $m-1$ others that don't violate the spacing requirement. I'm not sure how I can do this in $O(n)$ time. Is it possible?
As Yuval Filmus said in the comment, you can solve the optimization version (finding maximum viable $m$, which is a stronger version) by dynamic programming.

Let $m_i$ be the maximum viable elements of the sub-problem on $s[1..i]$. Consider the sub-problem on $s[1..i]$. An optimal solution has two choices.


It excludes $s[i]$, then it must choose an optimal solution of the sub-problem on $s[1..(i-1)]$.
It includes $s[i]$, then it cannot include $s[i-1],\ldots,s[i-k+1]$, and must choose an optimal solution of the sub-problem on $s[1..(i-k)]$.


Now you can write a recursion formula for $m_i$, and compute $m_1,\ldots,m_n$ in order in $O(n)$ time.