Algorithm to search for the tenth longest sequence of spaces in a given string

Question

Looking for an algorithm to find the length of the longest sequence of spaces in a given string, considering as few characters as possible?

Hint: your program should become faster as the length of the sequence of spaces increases.

I know a solution that is O (n) .. But is looking for a more optimal solution

Answer 1

You cannot find a solution that is less complex than O (n), because you need to go through each character in the worst case with an input line that contains no more than 0 or 1 consecutive spaces, or a complete space.

However, you can do some optimizations, but it will still be considered O (n).

For example:

Let M be the longest match as you go through your list. Also suppose you can access the input elements in O (1), for example, you have an array as input.

When you see spaces without spaces, you can skip M elements if current + M not a space. Of course, there cannot be spaces inside M.

And when you see a white character, if current + M-1 not a space, you know that you do not have the longest runs, you can also skip in this case.

Answer 2

But in the worst case (when all characters are empty) you need to examine each character. Therefore, it cannot be better than O (n) in complexity.

Rationale: Assume that the entire string is empty, you have not learned N characters and the outputs of your algorithms are n . Then, if any unoccupied character is not empty, your answer will be incorrect. So, for this particular input, you need to examine the entire line.

Answer 3

It is impossible to do this faster than O(N) in the worst case. However, here are a few optimizations involving indexing based on 0.

• If you already have a complete sequence of L spaces (upon completion I mean a sequence that is not a subsequence of a larger sequence), and L at least half the size of your line, you can stop.
• If you have a complete sequence of spaces L , as soon as you hit the space in position i , check if the character in position i + L also a space. If so, continue scanning from position i forward, as you can find a larger sequence - however, if you encounter a space to position i + L , you can go directly to i + L + 1 . If this is not a space, you cannot build a large sequence starting with i , so scanning starts with i + L + 1 .
• If you have a complete sequence of spaces of length L , and you are in position i , and you have k positions left to check, and k <= L , you can stop the search, since obviously you can no longer find anything it's better.

To prove that you cannot do it faster than O(N) , consider a line that does not contain spaces. You will need to access each character once, so it is O(N) . Same thing with a string that contains only spaces.

Answer 4

The obvious idea: you can jump over K + 1 places (where K is the longest time sequence) and scan back if you find a space.

So you have something about verified (n + n / M) / 2 = n (M + 1) / 2M positions.

Edit:
Another idea would be to use a kind of binary search. It looks like this: for a given k, you create a procedure that checks to see if there is a sequence of spaces with a length> = k. This can be achieved using steps O (n / k). Then you try to find the maximum k with binary search.

Edit:
During subsequent searches, you can use the knowledge that a sequence of some length k already exists and start skipping at k from the very beginning.

Answer 5

Whatever you do, the worst case is always o (n) - if these spaces are in the last part of the line ... (or the last "checked" part of the line).