题解 | #字母矩阵#

思路

二维矩阵前缀和，sum[i][j][l]代表在以（i,j）右下角点的矩形中第l个字母的数量，二分正方形的边长，看在这个边长中能否找到一个正方形满足条件。

代码

import java.io.BufferedInputStream;
import java.util.Arrays;
import java.util.Scanner;

public class Main{
    public static void main(String[] args){
        Solve s=new Solve();
        s.solve();
    }
}
class Solve{
    int n,m;
    int[][][] sum;
    public void solve(){
        Scanner s=new Scanner(new BufferedInputStream(System.in));
        n=s.nextInt();
        m=s.nextInt();
        int k=s.nextInt();
        s.nextLine();
        char[][] chars=new char[n][m];
        for (int i = 0; i <n ; i++) {
            String str=s.nextLine();
            for (int j = 0; j <m ; j++) {
                chars[i][j]=str.charAt(j);
            }
        }
        System.out.println(getAns(chars,k));
    }
    private int getAns(char[][] chars,int k){
        sum=new int[n+1][m+1][26];
        for (int i = 1; i <=n ; i++) {
            for (int j = 1; j <=m ; j++) {
                for (int l = 0; l <26 ; l++) {
                    sum[i][j][l]=sum[i-1][j][l]+sum[i][j-1][l]-sum[i-1][j-1][l];
                }
                sum[i][j][(chars[i-1][j-1]-'a')]++;
            }
        }
        int l=1,r=Math.min(n,m);
        int ans=-1;
        while (l<=r){
            int mid=(l+r)/2;
            if (check(mid,k)){
                ans=mid;
                r=mid-1;
            }else{
                l=mid+1;
            }
        }
        return ans;
    }
    boolean check(int len,int k){
        for (int i = 0; i <=n-len ; i++) {
            for (int j = 0; j <=m-len ; j++) {
                int[] cnt=get(i,j,len);
                if (getCount(cnt)>=k)return true;
            }
        }
        return false;
    }
    private int getCount(int[] cnt){
        int count=0;
        for (int i = 0; i <cnt.length ; i++) {
            if (cnt[i]!=0)count++;
        }
        return count;
    }
    int[] get(int x1,int y1,int len){
        int x2=x1+len;
        int y2=y1+len;
        int[] ans=new int[26];
        for (int i = 0; i <26 ; i++) {
            ans[i]=sum[x2][y2][i]-sum[x1][y2][i]-sum[x2][y1][i]+sum[x1][y1][i];
        }
        return ans;
    }
}