Sunday, August 28, 2011

Longest consecutive substring of 0 and 1

Given and Array of A[1..n] bits, find the length of longest consecutive substring of 0 and 1 such that number of 0s and 1s are equal 

temp=0;
1. For each index i, Just +1(the value of temp) when '1' is encountered; -1 in the other case and store in B[i];
2. Go through B, get each distinct value's min and max index
3. The biggest max - min is the result.

Sample:
Input: 1 0  0  0  0  1  1  1  0  0  1  0  1
B:     1 0 -1 -2 -3 -2 -1  0 -1 -2 -1 -2 -1

1: Min = Max = 0
0: Min = 1; Max = 7
-1: Min = 2; Max = 12
-2: Min = 3; Max = 11
-3: Min = Max = 4

The result is 10 :  0  0  1  1  1  0  0  1  0  1


3 comments:

  1. B[i] actually gives no of 1's more than no. of 0's at that index i.

    ReplyDelete
  2. A bit mistake in [ 0: Min = 1; Max = 7 ]. The min index of 0 should be set as -1. Simply consider "10", "0110".

    ReplyDelete
    Replies
    1. This comment has been removed by the author.

      Delete