import java.util.ArrayList;
import java.util.Arrays;
import java.util.List;
 
 class Main {
    public List<Integer> matchingCnt(int n, List<String> X) {
        int[][] g=new int[n][27];
        // n positions since any string can be any length and 26 characters
        // since abc and adb both have a at pos 0 then it can be counted 
        //so at the 0th j position we have count of 1 for a position .. also at 0 so g[0][0]=1
        List<Integer> res=new ArrayList<>();
        for( int i=0;i<n;i++){
            res.add(0);
        }
        // time is n*d where d is max length of string .. so time is O(N)
        // space is O(26*N)~O(N)
        for(int i=n-1;i>=0;i--){
            String s=X.get(i);
            int d=s.length();
            int c=0;
            for(int j = 0; j < d; j++){
                int x = s.charAt(j)-'a';
                c+=g[i][x];
                g[i][x]++;
            }
            res.set(i,c);
        }
        return new ArrayList<>();
    }
    public static void main(String[] args) {
        Main sol = new Main();
        int n = 3;
        List<String> X = Arrays.asList("abc", "ade", "abc");
        List<Integer> result = sol.matchingCnt(n, X);
 
        for (int i : result) {
            System.out.print(i + " ");
        }
    }
}
 

CmltcG9ydCBqYXZhLnV0aWwuQXJyYXlMaXN0OwppbXBvcnQgamF2YS51dGlsLkFycmF5czsKaW1wb3J0IGphdmEudXRpbC5MaXN0OwoKIGNsYXNzIE1haW4gewogICAgcHVibGljIExpc3Q8SW50ZWdlcj4gbWF0Y2hpbmdDbnQoaW50IG4sIExpc3Q8U3RyaW5nPiBYKSB7CiAgICAgICAgaW50W11bXSBnPW5ldyBpbnRbbl1bMjddOwogICAgICAgIC8vIG4gcG9zaXRpb25zIHNpbmNlIGFueSBzdHJpbmcgY2FuIGJlIGFueSBsZW5ndGggYW5kIDI2IGNoYXJhY3RlcnMKICAgICAgICAvLyBzaW5jZSBhYmMgYW5kIGFkYiBib3RoIGhhdmUgYSBhdCBwb3MgMCB0aGVuIGl0IGNhbiBiZSBjb3VudGVkIAogICAgICAgIC8vc28gYXQgdGhlIDB0aCBqIHBvc2l0aW9uIHdlIGhhdmUgY291bnQgb2YgMSBmb3IgYSBwb3NpdGlvbiAuLiBhbHNvIGF0IDAgc28gZ1swXVswXT0xCiAgICAgICAgTGlzdDxJbnRlZ2VyPiByZXM9bmV3IEFycmF5TGlzdDw+KCk7CiAgICAgICAgZm9yKCBpbnQgaT0wO2k8bjtpKyspewogICAgICAgICAgICByZXMuYWRkKDApOwogICAgICAgIH0KICAgICAgICAvLyB0aW1lIGlzIG4qZCB3aGVyZSBkIGlzIG1heCBsZW5ndGggb2Ygc3RyaW5nIC4uIHNvIHRpbWUgaXMgTyhOKQogICAgICAgIC8vIHNwYWNlIGlzIE8oMjYqTil+TyhOKQogICAgICAgIGZvcihpbnQgaT1uLTE7aT49MDtpLS0pewogICAgICAgICAgICBTdHJpbmcgcz1YLmdldChpKTsKICAgICAgICAgICAgaW50IGQ9cy5sZW5ndGgoKTsKICAgICAgICAgICAgaW50IGM9MDsKICAgICAgICAgICAgZm9yKGludCBqID0gMDsgaiA8IGQ7IGorKyl7CiAgICAgICAgICAgICAgICBpbnQgeCA9IHMuY2hhckF0KGopLSdhJzsKICAgICAgICAgICAgICAgIGMrPWdbaV1beF07CiAgICAgICAgICAgICAgICBnW2ldW3hdKys7CiAgICAgICAgICAgIH0KICAgICAgICAgICAgcmVzLnNldChpLGMpOwogICAgICAgIH0KICAgICAgICByZXR1cm4gbmV3IEFycmF5TGlzdDw+KCk7CiAgICB9CiAgICBwdWJsaWMgc3RhdGljIHZvaWQgbWFpbihTdHJpbmdbXSBhcmdzKSB7CiAgICAgICAgTWFpbiBzb2wgPSBuZXcgTWFpbigpOwogICAgICAgIGludCBuID0gMzsKICAgICAgICBMaXN0PFN0cmluZz4gWCA9IEFycmF5cy5hc0xpc3QoImFiYyIsICJhZGUiLCAiYWJjIik7CiAgICAgICAgTGlzdDxJbnRlZ2VyPiByZXN1bHQgPSBzb2wubWF0Y2hpbmdDbnQobiwgWCk7CgogICAgICAgIGZvciAoaW50IGkgOiByZXN1bHQpIHsKICAgICAgICAgICAgU3lzdGVtLm91dC5wcmludChpICsgIiAiKTsKICAgICAgICB9CiAgICB9Cn0K