I’m solving this problem: CSES - All Letters Square Subgrid Count

My idea uses a DP-based approach with O(n²·k) complexity, but it gives TLE for n = 3000, k = 26.

Currently, for every character, I am calculating the minimum side length of square required to include the character from each (i,j) cell, considering (i,j) as the top-left(starting) cell of the subgrid

My Code :- ~~~~~

#include <bits/stdc++.h>
using namespace std;
 
int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
 
    int n, k;
    if (!(cin >> n >> k)) return 0;
    vector<string> grid(n);
    for (int i = 0; i < n; ++i) cin >> grid[i];
 
    // Use flattened arrays. val has shape (n+1) x (n+1) to avoid bounds checks.
    const int W = n + 1;
    const int INF = n + 5;
 
    // mn[i*n + j] will store S(i,j) = max_c s_c(i,j)
    vector<int> mn(n * n, 0);
 
    // temporary val array for each letter (size (n+1)*(n+1))
    vector<int> val((n + 1) * (n + 1));
 
    for (int c = 0; c < k; ++c) {
        // initialize border to INF
        std::fill(val.begin(), val.end(), INF);
 
        int ch = 'A' + c;
        // compute from bottom-right to top-left
        for (int i = n - 1; i >= 0; --i) {
            int base = i * W;
            for (int j = n - 1; j >= 0; --j) {
                int idx = base + j;
                if (grid[i][j] == (char)ch) {
                    val[idx] = 1;
                } else {
                    // neighbors: right (idx+1), down (idx+W), diag (idx+W+1)
                    int a = val[idx + 1];
                    int b = val[idx + W];
                    int d = val[idx + W + 1];
                    int mn3 = a < b ? a : b;
                    mn3 = mn3 < d ? mn3 : d;
                    val[idx] = 1 + mn3;
                }
            }
        }
 
        // update global mn (keep maximum across letters)
        for (int i = 0; i < n; ++i) {
            int baseGrid = i * n;
            int baseVal = i * W;
            for (int j = 0; j < n; ++j) {
                int s_c = val[baseVal + j];
                // s_c might be INF if letter doesn't appear in bottom-right region
                if (s_c > n + 1) s_c = INF; // keep it large
                int idx = baseGrid + j;
                if (s_c > mn[idx]) mn[idx] = s_c;
            }
        }
    }
 
    // compute final answer
    long long ans = 0;
    for (int i = 0; i < n; ++i) {
        int base = i * n;
        for (int j = 0; j < n; ++j) {
            int idx = base + j;
            int sneed = mn[idx];
            if (sneed >= INF) continue; // some letter never appears in any bottom-right region -> impossible
            int r = min(n - i, n - j); // max possible side length
            if (sneed <= r) ans += (r - sneed + 1);
        }
    }
 
    cout << ans << '\n';
    return 0;
}

~~~~~

What’s the more efficient way or known approach to solve this problem?