Efficient algorithm to find the largest run of zeros in a binary string? [closed]

Question

I am looking for an efficient algorithm to find the longest run of zeros in a binary string. My implementation is in Python 2.7, but all I require is the idea of the algorithm.

For example, given '0010011010000', the function should return 4.

Answer 1

I don't think there is anything better than a single pass over the string, counting the current sequence length (and updating the maximum) as you go along.

If by "binary string" you mean raw bits, you can read them one byte at a time and extract the eight bits in there (using bit shifting or masking). That does not change the overall algorithm or its complexity.

Answer 2

It should be possible to beat the obvious algorithm. The idea is, if you already have a run of 0s of length N and you see two 1s at no more than N positions apart, you don't need to check any positions in between. So check a candidate sequence of zeroes from the end rather than from the beginning. In the very worst case you will just check all the elements, just as in the naïve method, but on the average it will be less than that.

So the algo goes like this (pseudocode, untested)

  maxrun = 0
  curpos = 0
  runstart = 0
  runend = 0

  while curpos + maxrun < array.length
      broken = false
      for i = curpos + maxrun, i >= curpos and not broken, --i
        if array[i] == 1
          broken = true
          curpos = i + 1

      if not broken
        runstart = curpos
        # found a longer run of 0s
        # now extend it to the end
        maxrun++
        curpos += maxrun
        while curpos < array.length and array[curpos] == 0
          maxrun++
        # ok found the 1 at the right end of the run
        # go to the next position and start over
        runend = curpos
        curpos++

 # the longest run of 0s is [runstart, runend)

Answer 3

To find the largest run of consecutive zeros in a binary string, I suggest the following outline:

int maxConsecutiveZeros(String binaryString) {
    int maxcount = Integer.MIN_VALUE;
    int currcount = 0;
    for(int i=0; i < binaryString.length(); i++) {
        if(binaryString.charAt(i) == '0') {
            currcount++;
        } else {
            maxcount = Math.max(currcount, maxcount);
            currcount = 0;
        }
    }
    return maxcount;
}

You should separately handle the case where binaryString ends in zero. Add that part to the provided outline and you are done.

The complexity of this approach is linear in the length of binary string.

Answer 4

It depends on what you mean by efficient.

If your intent is to minimise runtime, you'll basically have to go over the string character by character, analysing the runs of consecutive zeros and keeping track of the longest, something like:

def longRunZeros(s):
    big = 0
    curr = 0
    for c in s:
        if c == '0':
            curr += 1
        else:
            if curr > big:
                big = curr
            curr = 0
    if curr > big:
        big = curr
    return big

print longRunZeros('0010011010000')

If you're talking about programmer efficiency, just do:

def longRunZeros(s):
    return max(len(i) for i in s.split('1'))

instead.

It won't necessarily run the fastest but it'll free you up to have more time, perhaps to be used in analysing whether you even need raw speed for this operation. It'll also almost certainly be less prone to bugs to to its length.

As to whether you need the speed, consider this. With a 25M string, the character-by-character method takes 2.826 seconds CPU time for a million iterations. The split method takes 3.186 seconds for the same workload¹.

So, unless your string are a lot longer than 25M or you need to do it much more than a million times, it's not going to make a lot of difference, and I'd tend to opt for the method that's easier for me as a developer.

---

Addendum: after espousing how irrelevant differential performance is here, I feel a bit hypocritical mentioning that another method shown by John La Rooy in a comment actually seems to be a bit faster than both of mine.

But, for completeness, I'll suffer the slings and arrows to point that one out as well:

def longRunZeros(s):
    return len(max(s.split('1')))

That appears to average out at about 1.092 which is double the speed of the character-by-character case above.

---

¹ Those figures are averages of five runs, in my environment, and I make no guarantee they'll hold up anywhere else.

If you've ever been involved in optimisation efforts, you should know that it should be measured in your actual environments, rather than depending on the say-so of some random (but extremely good-looking) person on the internet :-)

Answer 5

A compiled regex might be decently fast, but I haven't really tested it. Nevertheless:

>>> binstr = '0010011010000'
>>> import re
>>> zeros = re.compile(r'0+')
>>> max(len(m) for m in zeros.findall(binstr))
4

Answer 6

This is a little bit messy and I know that if I thought a bit more I could improve the ending

def solution(N):
    y = [int(x) for x in bin(N)[2:]]
    lst,zero = [],0
    for r in y:
        if r == 0:
            zero +=1
        else:
            if zero > 0:
                lst.append(zero)
                zero = 0
    try:
        return max(lst)
    except Exception as E:
        return 0

You many not need the last part and just return max(lst)