# 2262. Total Appeal of A String
###### tags: `Leetcode` `Hard` `Count Subarray by Element`
Link: https://leetcode.com/problems/total-appeal-of-a-string/description/
## 思路
count subarray by elements
我们根据**每个字母能contribute多少个subarray**来解题
累加在一起就是答案
如果同一个字符串里有多个A出现，那么为了避免重复计数，我们约定，该字符串里关于A贡献的appeal只是由最左边的A给出。那么对于位置a处的字母A而言，假设它之前最近的一个字母A位于b，如下图

X X X A X X [A] X X X
      b      a

则确定由位置a上的A字符贡献appeal的substring，其左边界可以在“b右边”到“a左边”之间游动，其右边界可以在“a右边”到“最后一个字符右边”之间游动。所以组合的方案数是```(a-b)*(n-a)```.

综上，依次遍历所有的```nums[i]```，找到该字符能贡献appeal的字符串的左右边界范围，计算组合数目。最终将全部结果都加起来，返回答案。时间复杂度是$O(n)$.
## Code

class Solution {
    public long appealSum(String s) {
        int[] arr = new int[26];
        Arrays.fill(arr, -1);
        long ans = 0;
        int n = s.length();
        for(int i=0; i<s.length(); i++){
            ans += (i-arr[s.charAt(i)-'a'])*(n-i);
            arr[s.charAt(i)-'a'] = i;
        }
        return ans;
    }
}