original: link

Problem: 2262. 字符串的总引力

解题方法

目标： 计算输入字符串所有子字符串之独特小写字母数量
方法： 1. 对于每个小写字母char c，计算包含c的子字符串数量，加起来就是答案
2.但所有子字符串数量为len(s) * [len(s) + 1] / 2，计算不包含c的子字符串数量便可知包含c的子字符串数量
3.假设c在s中出现的索引为$p_1 \leq p_2 \leq \cdots \leq p_\lambda$，则不包含c的子字符串只能落在一对相邻的$s[p_i], s[p_{i+1}]$，或者$s[len(s)], s[-1]$之间，令$p_0 = -1, p_{\lambda + 1} = len(s)$，则包含c的子字符串数量为$$\frac{len(s) \times [len(s) + 1]} {2} - \sum_{1 \leq i \leq \lambda + 1} \frac{(p_i - p_{i-1}) \times (p_i - p_{i-1} - 1) }{2}$$

4.代码中遍历字符串，维护每个小写字母的最新索引即可

复杂度

• 时间复杂度:

$O(len(s))$

• 空间复杂度:

$O(1)$

Code

class Solution {
private:
    inline static long long cal(long long l, long long r) {
        return (r - l) * (r - l - 1) / 2;
    }
public:
    long long appealSum(string s) {
        const int n = s.length();
        long long ans{13ll * n * (n + 1)};
        array<int, 26> las{};
        std::fill(las.begin(), las.end(), -1);
        // 加入s第0个字符左边的位置(-1)
        for (int i = 0; i < n; ++i) {
            int _{s[i] - 'a'};
            ans -= cal(las[_], i);
            las[_] = i;
        }
        for (int i = 0; i < 26; ++i)
            ans -= cal(las[i], n);
        // 加入s最后字符右边的位置(s.length())
        return ans;
    }
};