#include #include #include using namespace std; int main() { ios_base::sync_with_stdio(false); cin.tie(nullptr); int H, W, K; cin >> H >> W >> K; vector grid(H); for (int i = 0; i < H; ++i) { cin >> grid[i]; } int result = 0; int max_size = min(H, W); for (int s = 1; s <= max_size; ++s) { vector> cnt(W, vector(26, 0)); vector> col_has(W, vector(26, false)); // Initialize for the first window (i=0) for (int j = 0; j < W; ++j) { for (int i_row = 0; i_row < s; ++i_row) { char c = grid[i_row][j]; cnt[j][c - 'a']++; } for (int c = 0; c < 26; ++c) { col_has[j][c] = cnt[j][c] > 0; } } for (int i = 0; i <= H - s; ++i) { if (i > 0) { // Update each column's cnt and col_has for (int j = 0; j < W; ++j) { // Remove the top row (i-1) char old_char = grid[i-1][j]; cnt[j][old_char - 'a']--; // Add the new bottom row (i + s - 1) char new_char = grid[i + s - 1][j]; cnt[j][new_char - 'a']++; // Update col_has for old_char and new_char col_has[j][old_char - 'a'] = cnt[j][old_char - 'a'] > 0; col_has[j][new_char - 'a'] = cnt[j][new_char - 'a'] > 0; } } // Process the sliding window in columns vector total(26, 0); int unique = 0; // Initialize the first s columns for (int c = 0; c < 26; ++c) { for (int j = 0; j < s; ++j) { if (col_has[j][c]) { total[c]++; } } if (total[c] > 0) { unique++; } } if (unique == K) { result++; } // Slide the window to the right for (int j = 1; j <= W - s; ++j) { int left = j - 1; int right = j + s - 1; // Remove the leftmost column for (int c = 0; c < 26; ++c) { if (col_has[left][c]) { total[c]--; if (total[c] == 0) { unique--; } } } // Add the new rightmost column for (int c = 0; c < 26; ++c) { if (col_has[right][c]) { total[c]++; if (total[c] == 1) { unique++; } } } if (unique == K) { result++; } } } } cout << result << '\n'; return 0; }