题解 | abb

#include <iostream>
#include <vector>
#include <string>
using namespace std;

int main() {
    int n;
    string s;
    cin >> n >> s;

    vector<vector<int>> prefix_counts(n + 1, vector<int>(26, 0));
    vector<int> current(26, 0);
    for (int i = 0; i < n; ++i) {
        char ch = s[i];
        prefix_counts[i] = current;
        current[ch - 'a']++;
    }
    prefix_counts[n] = current;

    vector<vector<int>> suffix_counts(n, vector<int>(26, 0));
    current = vector<int>(26, 0);
    for (int i = n - 1; i >= 0; --i) {
        char ch = s[i];
        suffix_counts[i] = current;
        current[ch - 'a']++;
    }

    long long ans = 0;
    for (int i = 0; i < n; ++i) {
        char c = s[i];
        int idx = c - 'a';
        int pre_total = i;
        int pre_c_count = prefix_counts[i][idx];
        int sum = pre_total - pre_c_count;
        int suf_c_count = suffix_counts[i][idx];
        ans += (long long)sum * suf_c_count;
    }

    cout << ans << endl;
    return 0;
}

https://www.nowcoder.com/discuss/727521113110073344

思路：

1. 前缀数组: prefix_counts 数组保存每个位置之前的各字符出现次数。通过遍历字符串，逐步更新当前字符计数并保存到前缀数组中。
2. 后缀数组: suffix_counts 数组保存每个位置之后的各字符出现次数。通过逆序遍历字符串，逐步更新当前字符计数并保存到后缀数组中。
3. 计算贡献: 对于每个位置，计算其作为中间字符时的有效子序列数量，即前导不同字符数乘以后续相同字符数，累加到总结果中。