O(n*m) C++ Short Solution


#1

int Solution::solve(vector &a) {
int n=a.size();
int m=a[0].length();
int ans=0;
int h1[m][3]={};
int h2[m][3]={};
memset(h1,-1,sizeof(h1));
memset(h2,-1,sizeof(h2));
map<char,int> ind;
ind[‘r’]=0;
ind[‘g’]=1;
ind[‘b’]=2;

for(int i=0;i<n;i++){
    h1[0][ind[a[i][0]]]=max(h1[0][ind[a[i][0]]], 0);
}
for(int j=1;j<m;j++){
    for(int k=0;k<3;k++)
    h1[j][k]=(h1[j-1][k]!=-1?h1[j-1][k]+1:-1);
    for(int i=0;i<n;i++){
        h1[j][ind[a[i][j]]]=max(h1[j][ind[a[i][j]]], 0);
    }
}
for(int i=0;i<n;i++){
    h2[m-1][ind[a[i][m-1]]]=max(h2[m-1][ind[a[i][m-1]]], 0);
}
for(int j=m-2;j>=0;j--){
    for(int k=0;k<3;k++)
    h2[j][k]=(h2[j+1][k]!=-1?h2[j+1][k]+1:-1);
    for(int i=0;i<n;i++){
        h2[j][ind[a[i][j]]]=max(h2[j][ind[a[i][j]]], 0);
    }
}

int mx[m][3];
int mn[m][3];
for(int i=0;i<m;i++){
    for(int k=0;k<3;k++){
        mn[i][k]=INT_MAX;
        mx[i][k]=INT_MIN;
    }
}
for(int j=0;j<m;j++){
    for(int i=0;i<n;i++){
        mn[j][ind[a[i][j]]]=min(mn[j][ind[a[i][j]]] , i);
        mx[j][ind[a[i][j]]]=max(mx[j][ind[a[i][j]]] , i);
    }
}

for(int i=0;i<m;i++){
    for(int k=0;k<3;k++){
        for(int j=0;j<3;j++){
            if(j==k || mn[i][k]>1000 || mx[i][j]<0)continue;
            if(h1[i][3-j-k]!=-1){
                ans=max({ans,abs(mx[i][j]-mn[i][k]+1)*(h1[i][3-j-k]+1)});
            }
            if(h2[i][3-j-k]!=-1){
                ans=max({ans,abs(mx[i][j]-mn[i][k]+1)*(h2[i][3-j-k]+1)});
            }
        }
    }
}

return (ans+1)/2;

}