Efficient algorithm to find number of sequences in string

Question

Suppose I have a string that goes like "abcabcdeaabcdef", where each character is either one more than the previous one or a.

If the character at position i is "c", I know that it is preceded by "ab".

I want to find the number and length of all sequences (substrings that contain sequential characters). For example, the above string would give "abc", "abcde", "a", "abcdef".

Is there a more efficient algorithm to do this than simply doing a O(n) search over the string?

• quicksort: Under usual assumptions, taking $o(n)$ time means that your algorithm can't read the entire string, since the correct answer depends on all characters, this means it will fail on some input. Intuitively, you can't get away with not reading the input unless the answer is local to some subset of it or some additional hypotheses holds.
• letmutx: Why isn't "ab" a valid sequence?
• paparazzo: You are going to have to read the characters to get the sequence
• greybeard: Worst case? an, with no way to know without checking every character.

Answer 1

You cant create an algoithm to do this in the worst case. Even if we read right to left and if we assume we can do some level of jumping (e.g if we see an f we can jump 6 spaces left) we still have to, in the worst case (the string of a's), read over the entire string. This can never be done in $o(n)$ time. The right to left with skipping will run in $O(m)$ time where $m$ is the number of increasing subsequences, and $m$ is $O(n)$.

Answer 2

Hmm i don't think so.Let's suppose there exists algorithm which does less then (n-2) comprehensions and gives a correct answer. (we assume we never get empty input and our input always starts with a thats why n-2)

Let's define 2 inputs A = aaaaaaa... and B = aaa....b...a.aaa

Of course f(a) = n and f(b) = n - 1 where f is our algorithm.

Let's play a game with our Alghoritm:

Let's define function g(x) = 1 if input[x] = a, 0 otherwise.

Each call to g is one comprehension. We can easily construct 2 inputs with different numer of sequences which would have identical result of n-2 calls of g