CODEWITHSUNDEEP
stringalgorithm
Maclean Pinto
Maclean Pinto

Reputation: 1135

Given a binary string "10110". Find the count of all the substring with number of set bit count >= n

We could solve this question in brute force, taking all possible substrings and checking if the set bit count is greater n.

I was asked to solve this in o(n). I could not find any answer which could achieve this in o(n).

Is it possible to get all possible substrings of binary string in 0(n)?

Upvotes: 1

Views: 3445

Answers (3)

MBo
MBo

Reputation: 80197

Answer changed (noticed >= in problem statement).

Make two indices - left and right.

We want to account substrings starting from position left containing at least k ones.

At first move right until bit count reaches k.

Now we have some "good" substrings starting at left and ending in any position after right, so we can add len(s) - right + 1 to result.

Increment left by 1 until the next one.

Repeat moving right and so on. Algorithm is linear.

Python example:

s = '0010110010'
#s = '110010110010'
k = 2
left = 0
right = 0
res = 0
cnt = 0
while right < len(s):
    while (right < len(s)) and (cnt < k):
        if s[right] == "1":
            cnt += 1
        right +=1
    while (left <= right) and (cnt >= k):
        addend = len(s) + 1 - right
        res += addend
        print(left, right, addend, res)  #intermediate debug output
        if s[left] == "1":
            cnt -= 1
        left +=1
print(res)

0 5 6 6
1 5 6 12
2 5 6 18
3 6 5 23
4 6 5 28
5 9 2 30
30

Upvotes: 3

n. m. could be an AI
n. m. could be an AI

Reputation: 119867

A useful approach is to ask yourself how many substrings have less than n bits set.

If you can answer this question, then the answer to the original question is right around the corner.

Why is the modified question easier to grasp? Because when you have a substring, say S, with exactly n bits set, then any substring that contains S will have at least n bits set, so you don't need to examine any of those.

So let's say you have a substring. If it has less than n bits set, you can grow it to accommodate more bits. If it has n or more bits set, it cannot grow, you must shrink it.

Suppose you start from the leftmost empty substring, start index 0, end index 0, length 0. (Of course it's a half-open interval). It has no bits set, so you can grow it. The only direction it can grow is to the right, by increasing its end index. It grows and grows and grows until it eats n 1-bits; now it must shrink. How should it shrink? Obviously shrinking it in the opposite direction (decreasing its end index) would accomplish nothing. You would arrive at a substring you have just examined! So you should shrink it from the left, by increasing its start index. So it shrinks and shrinks and shrinks until it excretes a 1-bit from its rear end. Now it has n-1 1-bits, and it can grow again.

It is not difficult to show that you would enumerate all strings with less than n bits set this way.

Upvotes: 2

CoolStack
CoolStack

Reputation: 33

let N = count of '1' And let M = count of '0'

int sum = 0 ;
for( int i = n ; i <= N; i++ ) sum += C(N,i) ;
sum *= 1<<M ;

sum is your answer.

Upvotes: 1

Related Questions