Solution
/*
============================================================================
Author : James Chen
Email : a.james.chen@gmail.com
Description : Find the largest subarray with equal number of 0's and 1's.
Created Data : 14-08-2013
Last Modified :
============================================================================
*/
#include <iostream>
#include <iomanip>
#include <unordered_map>
#include <string>
using namespace std;
string FingLongestSubarray(string& input)
{
int maps[] = {-1, 1};
int accSum(0);
unordered_map<int, pair<int, int>> um;
int start(-1), end(-1), maxDiff(0);
um[0] = make_pair(0, 0);
for(int i = 0; i < input.size(); ++i){
accSum += maps[input[i] - '0'];
if(um.find(accSum) == um.end()){
um[accSum] = make_pair(i + 1, i + 1);
}
else{
um[accSum] = make_pair(um[accSum].first, i + 1);
if(um[accSum].second - um[accSum].first > maxDiff){
maxDiff = um[accSum].second - um[accSum].first;
start = um[accSum].first;
end = um[accSum].second;
}
}
}
return (start == -1) ? string("") : input.substr(start, end -start);
}
void DoTest(string input)
{
cout << "The input is " << input << endl;
cout << "The output is " << FingLongestSubarray(input) << endl;
cout << "-------------------------" << endl;
}
int main(int argc, char* argv[])
{
DoTest("000");
DoTest("1111");
DoTest("001010101");
DoTest("0001010101");
DoTest("01010101");
DoTest("000000111010101");
DoTest("0000001110101011");
DoTest("00000011101010111111111111111");
return 0;
}
Output
The input is 000
The output is
-------------------------
The input is 1111
The output is
-------------------------
The input is 001010101
The output is 01010101
-------------------------
The input is 0001010101
The output is 01010101
-------------------------
The input is 01010101
The output is 01010101
-------------------------
The input is 000000111010101
The output is 000111010101
-------------------------
The input is 0000001110101011
The output is 00001110101011
-------------------------
The input is 00000011101010111111111111111
The output is 000000111010101111
-------------------------
Press any key to continue . . .
Problem
Find the largest subarray with equal number of 0's and 1's.
example 001010101
O(n) solution
Create a hash table, make accumulated sum key of the hash table, and a pair indices of start and end as the value.
Put accumulated sum into a hash table if the hash table does not contain the value.
If accumulated sum is already there, update the end index of subarray.
Ff the subarray has max length, update variables of start and end