**Solution:**

- Replace 0 with -1.
- Find the cumulative sum at each index.
- In the cumulative sum array if at some index sum is 0 that means from index 0 to current index number of 0 and 1 are same.
- If there are duplicates in the cumulative sum array that means the cumulative sum is 0 in between so there are equal number of 0s and 1s.
- Just find out the longest one and return it.

**Source Code:**

string longestSubStrWithEqual0and1(int *arr, int size)

{

string strResult = "";

map<int, int> mapIntToInt;

if(arr == NULL || size == 0)

return strResult;

int i=1;

int* cumSumArr = new int[size];

if(arr[0] == 1)

cumSumArr[0] = 1;

else if(arr[0] == 0)

cumSumArr[0] = -1;

else

return strResult; // Error as there is interger other than 0 and 1 in array

for(; i<size; ++i)

{

if(arr[i] == 0)

cumSumArr[i] = cumSumArr[i-1] + (-1);

else if(arr[i] == 1)

cumSumArr[i] = cumSumArr[i-1] + 1;

else

return strResult; // Error as there is interger other than 0 and 1 in array

}

int maxLen =0;

int startIndex = 0;

int endIndex = 0;

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

{

if(mapIntToInt.find(cumSumArr[i]) == mapIntToInt.end())

{

mapIntToInt[cumSumArr[i]] = i;

}

else

{

int len = i - mapIntToInt[cumSumArr[i]];

if(maxLen < len)

{

maxLen = len;

startIndex = mapIntToInt[cumSumArr[i]] + 1;

endIndex = i;

}

}

if(cumSumArr[i] == 0)

{

maxLen = i + 1;

startIndex = 0;

endIndex = i;

}

}

if(maxLen > 0)

{

for(i = startIndex; i <= endIndex; ++i)

{

strResult += ('0' + arr[i]); }

}

delete [] cumSumArr;

return strResult;

}

what's this line doin .. if(mapIntToInt.find(cumSumArr[i]) == mapIntToInt.end()) could u please explain??

ReplyDelete@karthiga1988...mapIntToInt is std Map... and if its find function return its end that is mapIntToInt.end()that means the element (cumSumArr[i]) is not in mapIntToInt.

ReplyDelete