1
2
3
4
5
6
7
8
9
10
11
12
13
14
class Solution {
    public long appealSum(String s) {
        Integer[] lastIdx = new Integer[26];
        long ans = 0;
        for (int i = 0; i < s.length(); i++) {
            char currLetter = s.charAt(i);
            int left = i - (lastIdx[currLetter - 'a'] != null ? lastIdx[currLetter - 'a'] : -1);
            int right = s.length() - i;
            ans += left * right;
            lastIdx[currLetter - 'a'] = i;
        }
        return ans;
    }
}

这个想法确实牛逼. 我想到了看每个char的贡献是多少, 但是没有想到如何避免重复. 这里用到的想法是如果一个string中出现多个重复的字符, 比如字符o重复了5次. 首先我们会遇到最左边的o, 我们看包含它的substring中它能做出多少贡献. 首先是只包含它一个o的, 其次是包含它和另一个o的, 以此类推. 最后是包含所有o的, 等于说包含第一个o的所有substring我们都计算过了. 等到遇到第二个o的时候, 我们取substring的时候就不能取包含第一个o的substring了, 否则就会重复计算, 此时第二个o同样是greedy, 把包含自己以及右边所有o的substring都算上. 第三个o的时候, 同样不能包含第一个和第二个o, 然后greedy.

时间复杂度: O(n)
空间复杂度: O(1) 数组长度是26, 因此是O(1)