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
Sunday, August 28, 2011
Longest consecutive substring of 0 and 1
Subscribe to:
Post Comments (Atom)
B[i] actually gives no of 1's more than no. of 0's at that index i.
ReplyDeleteA bit mistake in [ 0: Min = 1; Max = 7 ]. The min index of 0 should be set as -1. Simply consider "10", "0110".
ReplyDeleteThis comment has been removed by the author.
Delete