Any other solution?


#1

Is there any other solution for this problem because I am not understanding the solution given in the editorial.


#2

Just find the subarray with MAX(no.of zeros-no. of ones)

vector Solution::flip(string A) {
vector a;
int ones=0;int zeros=0; int max=INT_MIN;int start=0;int index=0;int ind=0;

for(int i=0;A[i]!='\0';i++){
    if(A[i]=='0'){
        zeros++;
    }else{
        ones++;
    }
    if(zeros-ones<0){
        start=i+1;
        zeros=0;ones=0;
    }
    //cout<<"zeros "<<zeros<<"ones "<<ones<<endl;
    if(max<(zeros-ones)){
        max=zeros-ones;
        ind=start;
        index=i;
    }
    
}
if(max>0){
a.push_back(ind+1);a.push_back(index+1);    
}

return a;

}


#3

Just count for number of 1s added (sum++ for addition sum-- for converting existing one in zero).
remember that both the indeces in correct answer would point to zeroes in origional string.

vector<int> Solution::flip(string A) 
{
    int a, b, sum, max, tmp;
    sum=max=0;
    a=b=tmp=1;
    for(int i=0; i<A.size(); i++)
    {
        if(A[i]=='1') 
        {
            if(!sum)
            {
                tmp=i+2;
                continue;
            }
            sum--;
        }
        else if(A[i]=='0')
        {
            sum++;
            if(sum>max) 
            {
                max=sum;
                b=i+1;
                a=tmp;
            }
        }
    }
    if(!max) return {};
    return {a, b};
}

#4

its simple you have to understand kadane’s algorithm then replace every 1 by -1 and every 0 by 1 and then find the largest possible positive sum and the corrosponding range.
here’s my code
vector Solution::flip(string v) {
int i,n,sum=0,max=INT_MIN,zero0=0,range=0,st=0,f=0,sti=0;
n=v.size();
vector a(n,0);
int temp=0;
vector p;
for(i=0;i<n;i++){
if(v[i]==‘1’){
a[i]=-1;
}
else{

        a[i]=1;
    }
}
    for(i=0;i<n;i++){
        sum+=a[i];
    //    cout<<"sum is "<<sum<<endl;
        if(sum<0){
            sum=0;
            
            f=0;
            continue;
        }
        if(a[i]==1){
           // one1++;
            if(f==0){
                st=i;
                f=1;
            }
        }
        if(sum>max){
            max=sum;
                range=i-st+1;
                sti=st;
         //   cout<<"range is "<<range<<endl;
         //   temp=one+one1-zero0;
        }
    //    cout<<"range is "<<range<<endl;
    }
   // cout<<"range is "<<range<<endl;
    if(max==INT_MIN){
        return p;
    }
    else{
     //   cout<<"range is "<<range<<endl;
       // cout<<"sti is "<<sti<<endl;
        p.push_back(sti+1);
        p.push_back(sti+range);
        return p;
    }

}


#5

vector Solution::flip(string A) {

int flg=0;
for(int p=0;p<A.size();p++)
{
    if(A[p]=='0')
    flg=1;
}
if(flg == 0)
{
    vector<int >v;
    return v;
}
int mxa=0;
int cc=1;

vector<int >count;
if(A[0]=='0')
count.push_back(0);

for(int i=0;i<A.size()-1;i++)
{
    if(A[i] == A[i+1])
    cc++;
    else
    {
        count.push_back(cc);
        cc=1;
    }
}
if(A[A.size()-1] != A[A.size()-2])
count.push_back(1);
else
count.push_back(cc);

// cout<<count.size()<<" nbh"<<endl;
vectorans;

int n = count.size();

cc=0;
for(int i=0;i<n;i++)
{
    if(i%2 == 0)
    {
       cc-=count[i];
       cc=max(cc,0);
    }
    else
    {
        cc+=count[i];
    }
    mxa=max(mxa,cc);
}
//cout<<mxa<<endl;

/* for(int i=0;i<count.size();i++)
cout<<count[i]<<" ";
cout<<endl;*/

int indicator=0;
int maxaa=-1;
int i;
cc=0;
for( i=0;i<n;i++)
{
    if(i%2 == 0)
    {
       cc-=count[i];
    }
    else
    {
        cc+=count[i];
    }
    maxaa=max(maxaa,cc);
     cc=max(cc,0);
    
    indicator += count[i];
    if(maxaa == mxa)
    break;
}

/* cout<<“tgt”<<endl;
cout<<indicator<<endl;
cout<<“fjfkf”<<endl;*/
int right = indicator ;
cc =0;
int left;
//cout<<right<<"-=-="<<endl;
for(i = right-1;i>=0;i–)
{
if(A[i] == ‘0’)
cc++;
else
cc–;

    if(cc == mxa)
    left = i+1;
    
}

// int left = indicator+1 ;
//cout<<left<<" "<<right<<endl;
if(right >=0 && left>=0)
{
ans.push_back(left);
ans.push_back(right);
return ans;
}
return ans;

}