A simple 0(n) solution


#1

vector Solution::flip(string A)
{
int length=A.size();
int sum=0,count=0,max=0,pos=0,back=0;
for(int i=0;i<length;i++)
{
if(A[i]==‘1’)
{
sum–;
count++;
}
if(A[i]==‘0’)
{
sum++;
count++;
if(max<sum)
{
max=sum;
pos=i+1;
back=count;
}
}
if(sum<0)
{
sum=0;
count=0;
}
}
if(max==0)
{
return {};
}
else
{
return {pos-back+1,pos};
}
}