CODEWITHSUNDEEP
algorithm
user2980096
user2980096

Reputation: 147

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

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.

Upvotes: 1

Views: 1064

Answers (1)

algrid
algrid

Reputation: 5954

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

Upvotes: 3

Related Questions