828. Count Unique Characters of All Substrings of a Given String

T: O(26n + n) -> O(n)
S: O(1)

class Solution {
    public int uniqueLetterString(String s) {
        int n = s.length();
        List<Integer>[] pos = new ArrayList[26]; // 26(max is n)
        for (int i = 0; i < 26; i++) {
            pos[i] = new ArrayList<>();
            pos[i].add(-1);
        }
        for (int i = 0; i < n; i++) { // O(n)
            char c = s.charAt(i);
            pos[c - 'A'].add(i);
        }
        for (int i = 0; i < 26; i++) {
            pos[i].add(n);
        }
        
        int result = 0;
        for (int i = 0; i < 26; i++) {
            List<Integer> indexList = pos[i];
            for (int index = 1; index < indexList.size() - 1; index++) {
                int prev = indexList.get(index-1);
                int cur = indexList.get(index);
                int next = indexList.get(index+1);
                result += (cur - prev)*(next - cur);
            }
        }
        return result;
    }
}

/*

record each char's postion
ex: 

ABA
for A
[-1 0 2 3]

1*2 = 2  -> then in [-1 0 2] -> means first A's range can have A is unique , so in this case, the subarray number is (currindex - prev index)*(next index - currindex) = (0-(-1))*(2-0) = 2 there are 2 subarray which includes unique A, A and AB

then in [0 2 3]
2*1 = 2 => BA and A


for incudes B's subaaray and B is unique
[-1 1 3]
2*2 = 4 (AB, B, BA, ABA)
-----------------------------------------------------------------------------------------------

ABC
ex:

A
[-1 0 3]
1*3 = 3
B
[-1 1 3]
2*2 = 4

C
[-1 2 3]
3*1 = 3

3+4+3 = 10

T: O(26n + n) -> O(n)

*/