###
Longest substring 0's & 1's

Given a string containing 0's and 1's. One would need to find the longest sub-string such that the count of 0's is equal to the count of 1's in the largest sub string.
0 1 0 1 0 0 0 1 0 1 0 1 0 |<------->| |<------->|

Here solution is either 0 1 0 1 0 1 or 1 0 1 0 1 0.

## 6 comments:

saavadikare ellarayum.

go discuss these with your geek friends. leave us normal people alone :(

will this work? or is it too many passes?

#!/usr/bin/perl

sub func

{

my $arg = $_[0];

if (length($arg)<=1) {

return("");

}

$argwin[0]=0;

$maxlength=length($arg);

$triallength=$maxlength;

if ($triallength % 2 == 1) {

$triallength--;

}

for (my $i=0;$i=2;$triallength=$triallength-2) {

for($trialbeginpos=0;$trialbeginpos<$maxlength-$triallength+1;$trialbeginpos++)

{

if($argwin[$trialbeginpos]==$argwin[$trialbeginpos+$triallength])

{

$ret=substr($arg,$trialbeginpos,$triallength);

return($ret);

}

}

}

return;

}

My solution is an O(n^2) solution. There might be a better solution than O(n^2).

longestSubstring( char a[] , int size )

{

int i=0,j=0 , zerocount=0,onecount=0;

int substrsize =0 ,startindex=0, endindex=0;

int maxsubstrsize =0 ;

for( i =0 ; i< size ; i++)

{

substrsize=0 ;

zerocount = onecount =0 ;

for( j =i ; j< size ; j++)

{

substrsize++;

if ( a[i] == '0' )

zerocount++;

else

onecount++;

if( (zerocount==onecount)&&(substrsize >maxsubstrsize))

{

maxsubstrsize= substrsize;

startindex=i ;

endindex = j ;

}

}

}

// print substring using startindex and endindex;

for ( i =startindex ; i <=endindex ; i++)

printf("%c",a[i]);

}

#include

int main()

{

int q[] = { 1,1,1,1,0,0,1,0,1,1,

0,0,0,1,0,1,1,1,1,1,

1,1,1,1,1,1,1,1,1,0,

0,0,0,0,0,0,0,0,0,0,

0,0,0,0,0,0,0,0,0,0,

0,0,0};

int n = sizeof(q)/sizeof(int); /* No of elements in q */

#define N_BY_2 ((sizeof(q)/sizeof(int)+1)/2)

int i;

int cur=0; /* Current substr under consideration */

int zeros_missed=0, ones_missed=0; /* Spare 0s and 1s found before current substr */

int len[N_BY_2] = {0,}; /* Length of substrings found */

int begin[N_BY_2]={-1,}; /* Begining of substrings found */

int maxlen=-2, maxbegin; /* Best substr */

for (i=0; i 0) {

/* 0 found and we have a spare leading 1 */

ones_missed--;

if (begin[cur]==-1)

begin[cur] = i-1;

else

begin[cur] -= 1;

len[cur]++;

if (!ones_missed && cur > 0) {

/* Consumed all spare 1's we had, merge with previous substr */

len[cur - 1] += len[cur];

begin[cur - 1] = begin[cur];

cur--;

}

i++;

}

else if (q[i] == 1 && zeros_missed > 0) {

/* 1 found and we have a spare leading 0 */

zeros_missed--;

if (begin[cur]== -1)

begin[cur] = i-1;

else

begin[cur] -= 1;

len[cur]++;

if (!zeros_missed && cur > 0) {

/* Consumed all spare 0's we had, merge with previous substr */

len[cur - 1] += len[cur];

begin[cur - 1] = begin[cur];

cur--;

}

i++;

} else

{

if (len[cur] !=-1 ) {

/* An end of a substr of atleast 2 digits! */

if (len[cur] > maxlen) {

/* Is it the best so far? */

maxlen = len[cur];

maxbegin = begin[cur];

}

/* Start looking for next substr */

cur++;

len[cur]=0;

begin[cur]= -1;

}

/* Collect leading spare 0s and 1s for the next/this substr */

if (q[i] == 0) zeros_missed++;

else if (q[i] == 1 ) ones_missed++;

i++;

}

}

}

if (len[cur] > maxlen) {

/* Is the final substr better? */

maxlen = len[cur];

maxbegin = begin[cur];

}

printf("Length = %d Begining index = %d\n", maxlen * 2, maxbegin);

}

Time complexity O(n), but has a space-complexity of O(n/2).

Hopefully it is correct.

Keep track of substrings found so far, and the no of leading zeros/ones skipped before this sub-string, so that we can add them to this string later, when we find unmatched ones/zeros, and eventually, if we use up all the unused leading zeros/ones we had, merge this sustr to the prev substr found and go on

Sorry for spamming. :)

BTW a correction to the solution, I think the unused 0s and 1s should be maintained for previous substr's as well. i.e., zerocount & onecount should also be made as arrays.

And the space complexity is O(n/3) not n/2

A simple looking, but interesting question. Thanks.

Post a Comment