Short Palindrome

• Time : O(n)
• Space : O(1) //constant

c++

int shortPalindrome(string s) {
    int dp[26][26] = {}; // how many possible matches a after b
    int dpp[26] = {}; // how many matched b c in dpp[index]
    int freq[26] = {};
    int res = 0, mod = 1e9 + 7;

    for(auto& ch : s) {
        int index = ch - 'a';

        //add a b c [ch] previous matched result
        // use char as d
        res = (res + dpp[index]) % mod;

        // update matched count
        // use char as c
        for(int i = 0; i < 26; i++)
            dpp[i] = (dpp[i] + dp[i][index]) % mod;

        // update how many machted next time
        // use char as b
        for(int i = 0; i < 26; i++)
            dp[i][index] = (dp[i][index] + freq[i]) % mod;

        // use char as a
        freq[index]++;
    }

    return res;
}