Python 3 solution

This problem is similar to Count Triplets

import string

from collections import defaultdict

def shortPalindrome(s): # Write your code here

# frequency of characters
chars = defaultdict(int) 
# frequency of substrings 'ij', e.g. pair['ij'] = 2
pairs = defaultdict(int) 
# frequency of substrings 'iJJ'
triples = defaultdict(int)
mod = 10**9 + 7
count = 0

for j in s:
    # triples[j] is the total number of substrings of 'jAA'
    # we have seen so far
    # e.g., 'jaa', 'jbb', 'jcc' etc, starting with 'j'
    count += triples[j]

    for i in set(string.ascii_lowercase):   
        triples[i] += pairs[i+j]
        pairs[i+j] += chars[i]

    chars[j] += 1    

return count % mod