  Given an arbitrary bitstream, we consider the problem of finding the longest
substring whose ratio of ones to zeroes equals a given value. The central
result of this paper is an algorithm that solves this problem in linear time.
The method involves (i) reformulating the problem as a constrained walk through
a sparse matrix, and then (ii) developing a data structure for this sparse
matrix that allows us to perform each step of the walk in amortised constant
time. We also give a linear time algorithm to find the longest substring whose
ratio of ones to zeroes is bounded below by a given value. Both problems have
practical relevance to cryptography and bioinformatics.
