Substring search with max 1's in a binary sequence

user_5202586 0
Viewed 217

Problem

The task is to find a substring from the given binary string with highest score. The substring should be at least of given min length.

score = number of 1s / substring length where score can range from 0 to 1.

Inputs:
1. min length of substring
2. binary sequence

Outputs:
1. index of first char of substring
2. index of last char of substring
Example 1:
input
-----
5
01010101111100

output
------
7
11

explanation
-----------
1. start with minimum window = 5
2. start_ind = 0, end_index = 4, score = 2/5 (0.4)
3. start_ind = 1, end_index = 5, score = 3/5 (0.6)
4. and so on...
5. start_ind = 7, end_index = 11, score = 5/5 (1) [max possible]
Example 2:
input
-----
5
10110011100

output
------
2
8

explanation
-----------
1. while calculating all scores for windows 5 to len(sequence)
2. max score occurs in the case: start_ind=2, end_ind=8, score=5/7 (0.7143) [max possible]
Example 3:
input
-----
4
00110011100

output
------
5
8

What I attempted

The only technique i could come up with was a brute force technique, with nested for loops

for window_size in (min to max)
  for ind 0 to end
    calculate score
    save max score

Can someone suggest a better algorithm to solve this problem?

language-agnostic algorithm
2 Answers

There's a few observations to make before we start talking about an algorithm- some of these observations already have been pointed out in the comments.

Maths

Take the minimum length to be M, the length of the entire string to be L, and a substring from the ith char to the jth char (inclusive-exclusive) to be S[i:j].

All optimal substrings will satisfy at least one of two conditions:

  • It is exactly M characters in length
  • It starts and ends with a 1 character

The reason for the latter being if it were longer than M characters and started/ended with a 0, we could just drop that 0 resulting in a higher ratio.

In the same spirit (again, for the 2nd case), there exists an optimal substring which is not preceded by a 1. Otherwise, if it were, we could include that 1, resulting in an equal or higher ratio. The same logic applies to the end of S and a following 1.

Building on the above- such a substring being preceded or followed by another 1 will NOT be optimal, unless the substring contains no 0s. In the case where it doesn't contain 0s, there will exist an optimal substring of length M as well anyways.

Again, that all only applies to the length greater than M case substrings.

Finally, there exists an optimal substring that has length at least M (by definition), and at most 2 * M - 1. If an optimal substring had length K, we could split it into two substrings of length floor(K/2) and ceil(K/2) - S[i:i+floor(K/2)] and S[i+floor(K/2):i+K]. If the substring has the score (ratio) R, and its halves R0 and R1, we would have one of two scenarios:

  • R = R0 = R1, meaning we could pick either half and get the same score as the combined substring, giving us a shorter substring.
    • If this substring has length less than 2 * M, we are done- we have an optimal substring of length [M, 2*M).
    • Otherwise, recurse on the new substring.
  • R0 != R1, so (without loss of generality) R0 < R < R1, meaning the combined substring would not be optimal in the first place.

Note that I say "there exists an optimal" as opposed to "the optimal". This is because there may be multiple optimal solutions, and the observations above may refer to different instances.

Algorithm

You could search every window size [M, 2*M) at every offset, which would already be better than a full search for small M. You can also try a two-phase approach:

  1. search every M sized window, find the max score
  2. search from the beginning of every run of 1s forward through a special list of ends of runs of 1s, implicitly skipping over 0s and irrelevant 1s, breaking when out of the [M, 2 * M) bound.

For random data, I only expect this to save a small factor- skipping 15/16 of the windows (ignoring the added overhead). For less-random data, you could potentially see huge benefits, particularly if there's LOTS of LARGE runs of 1s and 0s.

The biggest speedup you'll be able to do (besides limiting the window max to 2 * M) is computing a cumulative sum of the bit array. This lets you query "how many 1s were seen up to this point". You can then take the difference of two elements in this array to query "how many 1s occurred between these offsets" in constant time. This allows for very quick calculation of the score.

user_62210240

You can use 2 pointer method, starting from both left-most and right-most ends. then adjust them searching for highest score.
We can add some cache to optimize time.

Example: (Python)

binary="01010101111100"
length=5


def get_score(binary,left,right):
    ones=0
    for i in range(left,right+1):
        if binary[i]=="1":
            ones+=1
    score= ones/(right-left+1)
    return score
    
cache={}
def get_sub(binary,length,left,right):
    if (left,right) in cache:
        return cache[(left,right)]
    table=[0,set()]
    if right-left+1<length:
        pass
    else:
        scores=[[get_score(binary,left,right),set([(left,right)])],
                get_sub(binary,length,left+1,right),
                get_sub(binary,length,left,right-1),
                get_sub(binary,length,left+1,right-1)]
        for s in scores:
            if s[0]>table[0]:
                table[0]=s[0]
                table[1]=s[1]
            elif s[0]==table[0]:
                for e in s[1]:
                    table[1].add(e)
    cache[(left,right)]=table
    return table

result=get_sub(binary,length,0,len(binary)-1)

print("Score: %f"%result[0])
print("Index: %s"%result[1])

Output

Score: 1
Index: {(7, 11)}
user_136082280
Related