字母矩阵

class Solution:
    def check(self, n, m, s, k, pre):
        # s表示边长
        # pre[i][j][t]表示以array[i][j]为右下角元素，array[0][0]为左上角元素正方形内 字母t出现的次数
        for i in range(1, n+1):
            for j in range(1, m+1):
                if i + s -1 > n&nbs***bsp;j + s - 1 > m:
                    continue
                count = 0
                for t in range(26):  
                    if pre[i+s-1][j+s-1][t]-pre[i+s-1][j-1][t]-pre[i-1][j+s-1][t]+pre[i-1][j-1][t]>=1:
                        count += 1
                    if count >= k:
                        return True
        return False
    
    def  minSideLength(self, array, n, m, k):
        import math
        pre = [[[0]*26 for _ in range(m+1)] for _ in range(n+1)]
        for i in range(1, n+1):
            for j in range(1, m+1):
                for t in range(26):
                    pre[i][j][t] = pre[i-1][j][t] + pre[i][j-1][t] - pre[i-1][j-1][t]
                t = ord(array[i-1][j-1]) - ord("a")
                pre[i][j][t] += 1
        minS, maxS = int(math.sqrt(k)), min(n, m)
        res = -1
        while minS <= maxS:
            midS = (minS + maxS)>>1
            if self.check(n, m, midS, k, pre):
                maxS = midS -1
                res = midS
            else:
                minS = midS + 1
        return res
    
if __name__ == "__main__":
    [n, m, k] = list(map(int, input().strip().split()))
    array = []
    for i in range(n):
        string = input()
        array.append(string)
    s = Solution()
    res = s.minSideLength(array, n, m, k)
    print(res)