2484. Count Palindromic Subsequences

Given a string of digits s, return the number of palindromic subsequences of s having length 5. Since the answer may be very large, return it modulo 109 + 7.

Note:

• A string is palindromic if it reads the same forward and backward.
• A subsequence is a string that can be derived from another string by deleting some or no characters without changing the order of the remaining characters.

long long l[10101][10][10], r[10101][10][10];

class Solution {
public:
    int countPalindromes(string s) {
        memset(l, 0, sizeof l);
        memset(r, 0, sizeof r);
        vector<int> lfreq(10), rfreq(10);
        long long n = s.length(), res = 0, mod = 1e9 + 7;
        for(int i = n - 1; i >= 0; i--) {
            for(int j = 0; j < 10; j++) {
                for(int k = 0; k < 10; k++) {
                    r[i][j][k] = r[i+1][j][k];
                    if(j == s[i] - '0') r[i][j][k] += rfreq[k];
                    r[i][j][k] %= mod;
                }
            }
            rfreq[s[i]-'0']++;
        }
        for(int i = 0; i < n; i++) {
            for(int j = 0; j < 10; j++) {
                for(int k = 0; k < 10; k++) {
                    if(i) l[i][j][k] = l[i-1][j][k];
                    if(j == s[i] - '0') l[i][j][k] += lfreq[k];
                    l[i][j][k] %= mod;
                }
            }
            lfreq[s[i]-'0']++;
        }
        for(int i = 2; i < n - 2; i++) {
            for(int j = 0; j < 10; j++) {
                for(int k = 0; k < 10; k++) {
                    long long now = l[i-1][j][k] * r[i+1][j][k] % mod;
                    res = (res + now) % mod;
                }
            }
        }
        return res;
    }
};