Simple approach O(n^2)


#1

int Solution::solve(vector &A) {
if(A.size()<2)return 0;

int n = A.size();
int m = A[0].size();

int startR,startG,startB,endR,endG,endB;
startR = startG = startB = m;
endR = endG = endB = -1;
for(int i=0;i<n;++i)
{
    for(int j=0;j<m;++j)
    {
        if(A[i][j]=='r'){startR = min(startR,j);endR = max(endR,j);}
        else if(A[i][j]=='g'){startG = min(startG,j);endG = max(endG,j);}
        else if(A[i][j]=='b'){startB = min(startB,j);endB = max(endB,j);}
    }
}
if(startR==m||startG==m||startB==m)return 0;
int ans = 0;
for(int j=0;j<m;++j)
{
    for(int i=1;i<=3;++i)
    {
        if(i==1)//taking r as one vertex of triangle
        {
            
            //Idea is that we will set either 'g' or 'b' as second vertex of triangel
            //and then remaining will be third vertex
            // area of triangle  = (base)*(height)/2
            //if position of one vertex (here 'r') is fixed then 
            //base will be maximum when second vertex is at bottom-most or at top-most on the vertical line 
            //same is for height
            
            int gstart=INT_MAX,gend = INT_MIN,bstart = INT_MAX,bend = INT_MIN;
            for(int i=0;i<n;++i)
            {
                if(A[i][j]=='g'){gstart = min(gstart,i);gend = max(gend,i);}
                if(A[i][j]=='b'){bstart = min(bstart,i);bend = max(bend,i);}
            }
            for(int i=0;i<n;++i)
            {
                if(A[i][j]=='r')
                {
                    if(bstart!=INT_MAX&&bend!=INT_MIN)
                    {
                        int area ;
                        area = ((max(abs(i-bstart),abs(i-bend))+1) * (max(abs(j-startG),abs(j-endG))+1));
                        area = area%2?area/2+1:area/2; 
                        ans = max(ans,(area));
                    }
                    if(gstart!=INT_MAX&&gend!=INT_MIN)
                    {
                        int area ;
                        area = ((max(abs(i-gstart),abs(i-gend))+1) * (max(abs(j-startB),abs(j-endB))+1));
                        area = area%2?area/2+1:area/2;
                        ans = max(ans,(area));
                    }
                }
            }
        }
        else
        {
            if(i==2)//taking b as one vertex of triangle
            {
                int rstart = INT_MAX,gstart = INT_MAX,rend = INT_MIN,gend = INT_MIN;
                for(int i=0;i<n;++i)
                {
                    if(A[i][j]=='r'){rstart = min(rstart,i);rend = max(rend,i);}
                    if(A[i][j]=='g'){gstart = min(gstart,i);gend = max(gend,i);}
                }
                for(int i=0;i<n;++i)
                {
                    if(A[i][j]=='b')
                    {
                        if(rstart!=INT_MAX&&rend!=INT_MIN)
                        {
                            int area;
                            area = ((max(abs(i-rstart),abs(i-rend))+1) * (max(abs(j-endG),abs(j-startG))+1));
                            area = area%2?area/2+1:area/2;
                            ans = max((area),ans);
                        }
                        
                        if(gstart!=INT_MAX&&gend!=INT_MIN)
                        {
                            int area;
                            area = ((max(abs(i-gstart),abs(i-gend))+1) * (max(abs(j-endR),abs(j-startR))+1));
                            area = area%2?area/2+1:area/2;
                            ans = max((area),ans);
                        }
                    }
                }
            }
            else//taking g as one vertex of triangle
            {
                int rstart = INT_MAX,bstart = INT_MAX,rend = INT_MIN,bend = INT_MIN;
                for(int i=0;i<n;++i)
                {
                    if(A[i][j]=='r'){rstart = min(rstart,i);rend = max(rend,i);}
                    if(A[i][j]=='b'){bstart = min(bstart,i);bend = max(bend,i);}
                }
                for(int i=0;i<n;++i)
                {
                    if(A[i][j]=='g')
                    {
                        if(rstart!=INT_MAX&&rend!=INT_MIN)
                        {
                            int area;
                            area = ((max(abs(i-rstart),abs(i-rend))+1) * (max(abs(j-endB),abs(j-startB))+1));
                            area = area%2?area/2+1:area/2;
                            ans = max((area),ans);
                        }
                        
                        if(bstart!=INT_MAX&&bend!=INT_MIN)
                        {
                            int area;
                            area = ((max(abs(i-bstart),abs(i-bend))+1) * (max(abs(j-endR),abs(j-startR))+1));
                            area = area%2?area/2+1:area/2;
                            ans = max((area),ans);
                        }
                    }
                }
            }
        }
        
    }
}
return ans;

}