Algorithm to find lenth of longest sequence of blanks in a given string

Question

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

Hint : Your program should become faster as the length of the sequence of blanks increases.

I know the solution which is O(n).. But looking for more optimal solution

Answer 1

You won't be able to find a solution which is a smaller complexity than O(n) because you need to pass through every character in the worst case with an input string that has at most 0 or 1 consecutive whitespace, or is completely whitespace.

You can do some optimizations though, but it'll still be considered O(n).

For example:

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

When you see a non-whitespace you can skip M elements if the current + M is non whitespace. Surely no whitespace longer than M can be contained inside.

And when you see a whitepsace character, if current + M-1 is not whitespace you know you don't have the longest runs o you can skip in that case as well.

Answer 2

But in the worst case (when all characters are blank) you have to examine every character. So it can't be better than O(n) in complexity.

Rationale: assume the whole string is blank, you haven't examined N characters and your algorithms outputs n. Then if any non-examined character is not blank, your answer would be wrong. So for this particular input you have to examine the whole string.