C++ O(n) solution [Converted problem to array of integer 1,-1 and check for smallest sum possible]


#1

vector Solution::flip(string A) {
vectora(A.length());
int maxi=0,maxj=0,i1=0,j1=0,maxneg=0,sum=0;;
for(int i=0;i<A.length();i++)
{
if(A[i]==‘1’)
a[i]=1;
else
a[i]=-1;
}
for(int i=0;i<a.size();i++)
{
sum+=a[i];
if(sum > 0)
{
i1=i+1;
sum=0;
continue;
}
if(sum<maxneg)
{
maxneg=sum;
maxi=i1;
maxj=i;
//cout << maxi <<" “<<maxj<<”\n";
}
}
//cout << maxneg <<"\n";
vectoro;
if(maxneg!=0)
{
o.push_back(maxi+1);
o.push_back(maxj+1);
}
return o;
}