0
$\begingroup$

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?

$\endgroup$
  • 2
    $\begingroup$ 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. $\endgroup$ – quicksort Jan 17 '17 at 16:39
  • 1
    $\begingroup$ Why isn't "ab" a valid sequence? $\endgroup$ – letmutx Jan 17 '17 at 17:01
  • $\begingroup$ You are going to have to read the characters to get the sequence $\endgroup$ – paparazzo Jan 17 '17 at 21:33
  • $\begingroup$ Worst case? aⁿ, with no way to know without checking every character. $\endgroup$ – greybeard Jan 18 '17 at 19:50
2
$\begingroup$

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

$\endgroup$
0
$\begingroup$

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

$\endgroup$

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.