public static int shortPalindrome(String s) {
    // Write your code here
        int n = s.length();
        final int NUM_OF_CHARs = 26;
        final long MOD = 1000 * 1000 * 1000 + 7;
        long res = 0;
        
        long[] charsCount = new long[NUM_OF_CHARs];
        long[][] pairsCount = new long[NUM_OF_CHARs][NUM_OF_CHARs];
        long[] trippletsCount = new long[NUM_OF_CHARs];
        
        for (int i = 0; i < n; i ++) {
            char c = s.charAt(i);
            int cIdx = (int) (c - 'a');
    
    //in the last turn, the pattern was '*' 'c' 'c'
    //this turn's pattern turns into 'c' '*' '*' 
    //another 'c' is needed to complete the palindrome of 4 chars
    //so if current char satisfies, include the count of 'c' '*' '*' 
    
            res = (res + trippletsCount[cIdx]) % MOD;
            
            for (int j = 0; j < NUM_OF_CHARs; j++) {
                
    //below line usage should be to keep tab on '*' 'c' 'c' tripllets
    //it depends on pairsCount which monitors '*''c'
                
                trippletsCount[j] = (trippletsCount[j] + pairsCount[j][cIdx]) % MOD;
    
    //this pairsCount means finding pairs that are '*''c' ('c' as in currently parsing char)
    //this depends on the preceeding '*', not 'c' 
    //therefore it should be delay 1 turn, hence placed before charsCount update
    
                pairsCount[j][cIdx] = (pairsCount[j][cIdx] + charsCount[j]) % MOD;   
            }
            
    //this charsCount is straight forward, 
    //it is to track frequency of appeared CURRENT characters 'c'
     
            charsCount[cIdx]++;
        }
        
        return (int) (res % MOD);
    }