字符串的总引力

字符串的 引力 定义为：字符串中 不同 字符的数量。

例如，"abbca" 的引力为 3 ，因为其中有 3 个不同字符 'a'、'b' 和 'c' 。
给你一个字符串 s ，返回 其所有子字符串的总引力 。

子字符串 定义为：字符串中的一个连续字符序列。

1. 区间贡献法

从左往右遍历，优先计算左边同一字符做出的贡献，后面出现的相同字符不再计入贡献，被前面覆盖，只计算不受前面相同字符影响的区间
相比其他贡献法的题目更好计算，只需考虑左侧的辖域范围，右侧默认完全统辖
故需要记录每一类字符上一次出现的位置

class Solution {
public:
    long long appealSum(string s) {
        vector<int> lasts(26, -1);
        long long res = 0;
        for(int i = 0; i < s.size(); ++i) {
            res += 1ll * (i - lasts[s[i] - 'a']) * ((int)s.size() - i);
            lasts[s[i] - 'a'] = i;
        }
        return res;
    }
};

2. 转移法

考虑两组相邻的子串：以 s[i−1] 结尾的子串、以 s[i]结尾的子串。
以 s[i] 结尾的子串，可以看成是以 s[i−1] 结尾的子串，在末尾添加上 s[i] 组成。
从左往右遍历 s，考虑将 s[i] 添加到以 s[i−1] 结尾的子串的末尾。
添加后，这些以 s[i−1] 结尾的子串的引力值会增加的值，等价于方法一种s[i]统辖的左侧范围

class Solution {
public:
    long long appealSum(string &s) {
        long long ans = 0;
        vector<int> last(26, -1); // 初始化成 -1 
        for (int i = 0, sum = 0; i < s.size(); ++i) {
            sum += i - last[s[i] - 'a']; //以当前遍历位置为结尾的子字符串总吸引力
            ans += sum; //统计所有位置子字符串
            last[s[i] - 'a'] = i;//更新辖域
        }
        return ans;
    }
};