Find number of substrings in binary string having equal 1's and 0's

Question

I came across the following question,

Find the total number of substrings in a string which contain equal number of 1's and 0's. Also the substring should have consecutive 0's followed by consecutive 1's or vice versa.

For example,

1010 - 10,01,10

1100110- 1100,10,0011,01,10.

My initial idea was to use a n^2 loop to find all substrings and then check if the condition is satisfied. Obviously there must be a better solution to this as I could not pass all cases.

Please suggest ideas to improve on this. Thanks.

You say "the substring should have consecutive 0's followed by consecutive 1's or vice versa." but your examples don't follow that guideline. Please clarify the problem. — Prune
– Prune, Commented Nov 10, 2017 at 20:59
What I meant is that any substring should be counted only if it has a group of 0's followed by a group of 1's or a group of 1's followed by a group of 0's. for instance, in the 2 queries above, the valid substrings for 1010 would be 10,01,10 and the valid substrings for query 1100110 would be 1100,10,0011,01,10 — user2980096
– user2980096, Commented Nov 10, 2017 at 21:47
Ah -- so 0110 isn't acceptable; got it. You can divide the string at the middle; one half will be all 0s, and the other will be all 1s. — Prune
– Prune, Commented Nov 10, 2017 at 21:51

algrid · Accepted Answer · 2017-11-10 21:31:03Z

3

I’d suggest the following - iterating over you sequence for each consecutive sequence of 0’s or 1’s of length L(k) (except for the first one) add to the counter min(L(k), L(k-1)). The final value of the counter will be the number you’re looking for.

For your example 1100110

L = (2, 2, 2, 1)

And the sum is 2+2+1=5

answered Nov 10, 2017 at 21:31

algrid

6,0343 gold badges38 silver badges41 bronze badges

Sign up to request clarification or add additional context in comments.

Collectives™ on Stack Overflow

Find number of substrings in binary string having equal 1's and 0's

1 Answer 1

Comments

Your Answer

Hot Network Questions

Collectives™ on Stack Overflow

1 Answer 1

Comments

Your Answer

Sign up or log in

Post as a guest

Related