# 0828. Count Unique Characters of All Substrings of a Given String
###### tags: `Leetcode` `Medium` `Count Subarray by Element`
Link: https://leetcode.com/problems/count-unique-characters-of-all-substrings-of-a-given-string/description/
## 思路
和[2262. Total Appeal of A String](https://hackmd.io/JdYsGdTtRFapoMn5gkT2lg)差不多

我们把这类技巧称为**aggregate subarray by element**.当我们想累加若干个不同subarray的某种属性时，因为遍历subarray的复杂度较高，我们改为**遍历数组元素，反向计算每个元素对于总属性的贡献**。

我们考虑位于```s[i]```的字母A，能够给哪些substring的countUniqueChars提供这一分？显然，我们就是要寻找哪些substring仅包含这一个A。我们假设i之前最近的一个A在位置```j```，```i```之后最近的一个A在位置```k```，如下图

X X X X A [X X A X X] A X X 
        j      i      k

那么符合条件的substring的左边界可以在“```j```右边”到“```i```左边”之间游动；同理，这个substring的左边界可以在“```i```右边”到“```k```左边”之间游动。所以这样的substring的组合起来就有```(i-j)*(k-i)```个。

我们类似地对每一个```s[i]```这样处理，最终累加答案。这个解法的时间复杂度是o(N).
## Code

class Solution {
    public int uniqueLetterString(String s) {
        int n = s.length();
        List<List<Integer>> pos = new ArrayList<>();
        for(int i=0; i<26; i++) pos.add(new ArrayList<>());
        for(int i=0; i<26; i++) pos.get(i).add(-1);
        for(int i=0; i<n; i++) pos.get(s.charAt(i)-'A').add(i);
        for(int i=0; i<26; i++) pos.get(i).add(n);
        int ans = 0;
        for(int i=0; i<26; i++){
            for(int j=1; j<pos.get(i).size()-1; j++){
                ans += (pos.get(i).get(j)-pos.get(i).get(j-1))*(pos.get(i).get(j+1)-pos.get(i).get(j));
            }
        }
        return ans;
    }
}